Graph Connectedness Explained: Connected Strongly Connected and Weakly Connected

Neural Lantern

Hello there. Lets talk about graphs and whether they are connected or not or maybe whether they are strongly connected versus weakly connected. We look at undirected graphs first and show what makes a graph connected meaning every node can reach every other node by a path. We add edges and check the connections step by step while also noting subgraphs. Then we switch to directed graphs and explain strongly connected versus weakly connected. Strongly connected follows the edge directions for every path. Weakly connected ignores the directions and checks if the graph would still be connected. Examples show how adding edges changes the status of the graph.   00:00 Introduction to Graph Connectedness  00:01 Drawing Nodes and a Disconnected Graph  01:56 Defining a Connected Graph  03:21 Introducing Subgraphs  04:48 Adding Edges to Create a Connected Graph  06:32 Adding Directions to Create a Directed Graph  08:03 Strongly Connected Versus Weakly Connected  08:34 Removing an Edge to Show Disconnection  09:29 Checking and Achieving Weak Connectivity  11:18 Adding Edges to Create a Strongly Connected Graph  13:20 Confirming the Strongly Connected Graph  13:32 Conclusion  14:17 Outro and Subscribe Request   graph theory, connected graph, strongly connected graph, weakly connected graph, undirected graph, directed graph, graph connectedness, nodes and edges, graph paths, data structures, subgraphs, graph algorithms   =-=-=-=-=-=-=-=-=   Thanks for watching!   Find us on other social media here:  - https://www.NeuralLantern.com/social  - Twitter / X: https://x.com/NeuralLantern  - Rumble: https://rumble.com/c/c-3696939  - BitChute: https://www.bitchute.com/channel/pg1Pvv5dN4Gt  - Daily Motion: https://www.dailymotion.com/neurallantern  - Minds: https://www.minds.com/neurallantern/  - Odysee: https://odysee.com/@NeuralLantern:5   Please show your support!   - Buy me a coffee: https://ko-fi.com/neurallantern   - Subscribe + Sharing on Social Media  - Leave a comment or suggestion  - Subscribe to the Blog: https://www.NeuralLantern.com  - Watch the main "pinned" video of this channel for offers and extras

Transcript

00:01Hello there! Let's talk about graphs and whether they're connected or not or maybe whether they're

00:05strongly connected versus weakly connected versus not connected. You never know.

00:20Okay, so hopefully you've seen my previous videos by now where we just talked about the basics of

00:25graphs. I have like a blank sheet of paper here. I'm just going to start drawing a graph. Remember

00:30graphs are nodes and edges where the nodes are like little t-type data structures that can hold

00:36a specific type of value. So I'm going to say our nodes hold integers. I think I made that one

00:43too

00:44small. That's okay. And the edges could have weights or maybe not weights at all depending on if you

00:50have a weighted or an unweighted graph. So I'm just going to start duplicating my nodes a little bit.

00:55And I'm just going to make a random graph. I need to probably change these values. Technically your

01:01graphs should support duplicate values in the nodes but and also the weights. But I don't want to

01:07because it's it's easier to talk about the graph when all the values are distinct. So for starters

01:13we have a bunch of nodes and they're not really connected to each other. Is this a valid graph?

01:17Yeah, it is. It's just not a connected graph. So the terminology that we're going to use for

01:23undirected graphs, meaning the edges don't have direction, is going to be connected or not. You

01:29know, I usually just say a not connected graph or a disconnected graph. So just basically like

01:35connected or not connected. Okay, so this is a not connected graph. I'm going to say not connected.

01:45Not cinnamon. I'm thinking about food as usual. Um, so it's not a connected graph. Why is it not a

01:53connected graph? Well, to define what does it mean to be a connected graph? It just means that every

01:58single node can find a path to every single other node in an undirected graph. So we can just double

02:04check this real fast. We can say, you know, can node number two find a path to, uh, you know,

02:10let me put a question here. Let's say we're going to check. You should be checking all the nodes one

02:15by one by one to see if the node in particular can reach every other node. The first node that

02:20can't do it means the whole graph is not considered connected. So, you know, two, it can't reach one.

02:26So that means it's not a connected graph. So this is not a connected graph because one or more nodes

02:33violate the rule of you have to be able to reach every single other node. Okay. So that means if

02:38we want

02:38to connect a graph, we probably just have to start adding edges. So I'm going to go ahead and, uh,

02:44uh, let me, let me write the word connected here and then I can like either circle it or cross

02:48it

02:48out. So right now we have, no, this is not a connected graph. I'm going to start adding edges.

02:55We're going to stick with an undirected graph for now. So I'm going to connect, uh, two and one

03:00and, uh, two and nine, maybe one and 13. Uh, actually, you know what? I'm going to erase this edge

03:09and maybe connect these over here. And the thing is, this is a valid graph that you're looking at.

03:15It's just not a connected graph. Some other terminology, uh, I didn't mention in other

03:20videos is that, uh, we can have sub graphs. We have like a sub graph here and another sub graph

03:25here. Those are basically just two different portions of the same graph that appear to be

03:30connected within themselves. So those are sub graphs. Uh, you can probably tell right away that

03:35this is not a connected graph. You can, you can double check to be sure, you know, it's good to

03:40do things the hard way. So you don't get the wrong answer when you're really trying to figure

03:42something out. So let's look at two. Can two reach one? Uh, yes. So that's good. Can two reach

03:49nine? Yeah. It just hops to one and then hops to nine. So two can reach one and also nine.

03:55That's good. Can two reach three? Nope. So this is still not a connected graph.

04:01Okay. I'm going to add one more edge. Uh, and then we'll just check again.

04:06Where do you think I'm going to do it? Maybe if I add it, I'll add a funky edge going

04:11from 13 to like

04:12nine or something, just so it feels a little bit more awkward. Okay. Let's check one by one by one.

04:19Um, uh, let me actually get rid of this edge on the previous slide so we can still say that's

04:25not

04:25connected. Let's check one by one by one. Every node must be able to reach every single other node.

04:30So I'm going to look at two and I'm going to say, all right, uh, two, can it reach one?

04:36Yes. Uh,

04:37can it reach nine? Yes. We go from two to one to nine. So that's good. Can it reach three?

04:43Yeah.

04:43It can go from two, uh, to one to nine to 13 to three, and then it can reach three.

04:51And because we just

04:52saw that it went through 13 to reach three, that means two can reach every single other node.

04:59This is going to be more important, uh, as a double check, uh, when we have directed graphs in a

05:04second. So two is good. So the next thing you want to do is just move on to some other

05:10node and do the

05:11exact same process. You know, can, can nine reach a one? Yes. Okay. It can reach a one. Can it

05:18reach a

05:18two? Yeah. It goes through the one. Can it reach the 13? Yep. Can it reach the three?

05:22Yep. Okay. So we just checked every single destination node starting at the node nine,

05:26but here's a little bit of a shortcut. Try to find a node that is right next to a node

05:31that you know,

05:31can reach everything. And if the node in question is able to reach that previously, you know, connected

05:37a node or vertex, then we know that that node in particular is also connected. So what I'm saying

05:43is the one, instead of checking every single other node in the graph, which might be really hard

05:48if we have a whole bunch of nodes in our graph, um, we'll just ask, can the one reach the

05:53two?

05:54Because if it can, the two can reach everything. So that means the one actually can reach everything

05:59as well. So the one can reach the two. So the one is connected to everything. Uh, the three,

06:05the three can reach, uh, the one and the one can reach everything. I'm doing things the hard way on

06:10purpose just to prove a point. So the three can reach everything. The 13 can reach the three in one

06:15hop.

06:15So the 13 can reach everything. The nine, it can reach the one and it can reach the 13 in

06:21one hop.

06:21So the nine can also actually reach everything. So that means this is indeed a connected graph.

06:28Yay, we did it. Um, sorry about that. The next thing that we're going to do is add direction to

06:35our

06:35graph. You know, we could do like more examples, maybe leave a comment if you want me to do some

06:39super

06:40extra complicated examples for just a undirected and connected graph. I'm ignoring weight, by the way,

06:44cause it doesn't really matter for these purposes. So let's upgrade our graph. So, uh, maybe I should

06:51put a question mark here. That would have been a good idea. We're just asking, you know, is it

06:55connected or not? I'm going to take this existing graph and I'm just going to start, uh, adding

07:01direction to every single edge. Let's see if I'm following my notes, single node, do, do, do, do,

07:06do, sub graphs, right? Well, it wasn't connected at first and then we started adding. Okay. So that's

07:12basically, okay. Let's add direction to every single edge. Um, so every single edge has to

07:19have a direction or every single edge has to have no direction. You can't really mix and match.

07:23So I'm just going to go through every single edge and add a direction, uh, like this. And,

07:29you know, to be fair, I think I've said this in my other videos and undirected edge is kind of

07:33the

07:34same thing as a directed edge going in or two directed edges going in both directions. So this three

07:39and 13, what's going on with my computer? Hello, this three and 13 edge, uh, it would have kind of

07:46been the same as just having two edges going in opposite directions. So maybe I'll just do that

07:49right now for this huge, weird edge. I'm just going to put like an arrow over here instead of

07:54totally redrawing it. Then I double check that every single edge has a direction so that I have

07:59a valid graph. And now I can ask, uh, is this connected or not? Actually, when it comes to a

08:04directed

08:05graph, you don't really have connected or not anymore. You have, uh, strongly connected,

08:10whoops, strongly connected versus weakly connected. Um, maybe I should, uh, just separate these words

08:19and then just kind of like move them. So let's get rid of this, save this over here, move it

08:27down.

08:28So what am I talking about? Um, well, first, let me remove an edge real quick. I'll remove this edge

08:36right here. So now we have two sub graphs in this graph. You can tell for sure if this was

08:41an

08:41undirected graph, it would not be connected. But now that we're dealing with direction, we have to ask,

08:46is it strongly connected versus weakly? So what does strongly mean? Strongly connected means can every

08:52node reach every other node if you obey the direction of the edges? So that's clearly not true.

08:58There's no edge at all that even connects this one and nine. So it's definitely not strongly

09:02connected. Weakly connected on the other hand means if you temporarily ignore the direction of

09:08the edges, then could you consider the graph connected? So if we pretended that there were

09:13no arrows here, would we think that it's a connected graph? If the answer is yes, then it's at least

09:18a

09:18weakly connected graph. So this is not weakly connected because if this was an undirected graph, it's not

09:24even connected at all. So that sucks. I'm going to go ahead and add another edge here. So I'm going

09:30to add an edge from two to nine. So the first thing is, oh, sorry, I have to add another

09:36edge. Let me do

09:36from one to 13 for fun. So now the first thing is, let's check to see if this is a

09:41strongly connected

09:42graph. Right away, I can see that the two node is unreachable by any other node. So this is definitely

09:52not strongly connected because all the other nodes would be would have to be able to reach two. All

09:57right. So first thing you could do just to very quickly check is just look at every single node

10:01and ask, is it reachable, you know, by anything? And then after that, you can do things the hard

10:06way. So it's not strongly connected. What about weakly connected? If we ignore the direction of

10:11the graph, sorry, if we ignore the direction of the edges in this graph, then yeah, we could reach

10:17every single node from every other node. Let's, let's just double check that real fast. I'm going

10:22to say, you know, the two node, if we're ignoring direction, can it reach the one? Yes. Can it reach

10:29the 13? Yes. The three? Yes. Can it reach the nine? Yes. So that means the two node

10:36is sort of like weakly connected to every other node in the graph. Do the same thing for the one

10:40node. Previously, we just said, you know, check everything one by one or use a shortcut. So I'm

10:45going to use the shortcut. The one node, if we ignore direction can reach the two nodes. So I'm

10:50going to say the one is weakly connected, at least everything else. I'm not even going to check to see

10:55if it's strongly connected to everything else. I think the answer is no, but we do the same thing for

10:59the 13. The 13 can reach the one pretty fast. The three can reach the 13. The nine can reach

11:05the two.

11:05So every single node can weakly reach. That's not an official term. Every other node, which means

11:11this is a weakly connected graph. Okay, cool. How can we make this a strongly connected graph? Well,

11:19we just have to add a bunch of edges. So that's what I'm going to do. I'm going to kind

11:24of like a look

11:25at what is missing here. So we'll ask the two, can the two reach and let's obey the direction of

11:32the

11:32edges again. Can the two reach the one? Yes. Can the two reach the 13? Yes. Can it reach the

11:37three?

11:37Yes. Can the two reach the nine? Yes. So that means right now the two is strongly connected to

11:45everything else. So we're on track for a strongly connected graph. We then look at the one node and

11:50we realize that the one node, it can reach the 13 and the three, and it can also reach the

11:54nine,

11:54but it can't reach the two. That's one thing that was blocking us last time from saying strongly

12:00connected. So we just have to add another edge. If we want this to be a strongly connected graph,

12:05we have to figure out how can we get the one to reach the two? We can go through something

12:09if we

12:10want to, that's fine. We can also just write an edge that just goes back to the two, but that's,

12:15I don't know, that's kind of boring. I'm going to make an edge that goes from one to nine,

12:19and then I'm going to make an edge that goes from nine to two. So looking at the one node,

12:26it can now reach the two if we go through the nine. So that's good. Can the one reach the

12:32nine? Yes.

12:33Can the one reach the 13? Yes. Can the one reach the three? Yes. Okay. So the one node can

12:37now reach

12:38every single other node. So now we're a little bit more on track for a strongly connected graph.

12:45Look at the 13 node. Can it reach the one node? Actually, yes. If we go from 13 to nine,

12:52and then two, and then one, we can reach the one node. Since we know the one node is connected

12:57to

12:57everything else, we can now say that the 13 node is connected to everything else too. The three node

13:02is connected definitely to the 13. So I'll say three is connected to everything. The nine node can reach

13:08the two node, which is connected to everything. So that means the nine node is also connected to

13:12everything. And at this point, we now have a strongly connected graph. It's not weakly connected.

13:18It's stronger than that. Any questions? So let's see, we added a bunch of edges. I think maybe this

13:29is actually all we need to do for this particular video, because we're just going to talk about

13:32connectedness. About 15 minutes, not too bad. All right. So I think I'm going to leave it here.

13:39Drop a comment if you want to do way more complicated examples. If you want to provide me a sample

13:44graph,

13:44that's awful. And I could just I don't know, in the sometime in the future, I could record a video

13:48about it. Or just let me know your thoughts. Thank you so much for watching this video. I hope you

13:54had a little bit of fun. And I hope you learned a little bit of stuff. I'm outie, patowdie.

14:02All right, let's see this. Well, can you see that guy in the background? Oh, shoot.

14:11I'm just kidding. I set that as the screen saver.

14:40And grow this community. So we'll be able to do more videos, longer videos, better videos,

14:44or just I'll be able to keep making videos in general. So please do me a kindness and subscribe.

14:51You know, sometimes I'm sleeping in the middle of the night, and I just wake up because I know

14:55somebody subscribed or followed. It just wakes me up and I get filled with joy. That's exactly what

14:59happens every single time. So you could do it as a nice favor to me, or you could you could

15:04troll me if

15:04you want to just wake me up in the middle of the night, just subscribe. And then I'll just wake

15:07up.

15:08I promise that's what will happen. Also, if you look at the middle of the screen right now,

15:13you should see a QR code, which you can scan in order to go to the website, which I think

15:17is also

15:18named somewhere at the bottom of this video. And it'll take you to my main website where you can

15:22just kind of like see all the videos I published and the services and tutorials and things that I

15:27offer and all that good stuff. And if you have a suggestion for clarifications or errata or just future

15:37videos that you want to see, please leave a comment. Or if you just want to say, Hey, what's up?

15:41What's going on? You know, just send me a comment, whatever. I also wake up for those in the middle

15:45of the night. I get, I wake up in a cold sweat and I'm like, it would really, it really

15:50mean the

15:51world to me. I would really appreciate it. So again, thank you so much for watching this video

15:55and enjoy the cool music as, as I fade into the darkness, which is coming for us all.

19:07Am I recording?

19:08Yeah, I think I'm good.

19:11Hello there.

19:13Let's talk about whether a graph is connected or not, or maybe whether it's strongly connected

19:17or weakly connected or not connected at all.

19:20You never know.

Category

Transcript

Comments

Recommended