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
=-=-=-=-=-=-=-=-=
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
Hello there! Let’s talk about graphs and whether they’re connected or not or maybe whether they’re
strongly connected versus weakly connected versus not connected. You never know.
Okay, so hopefully you’ve seen my previous videos by now where we just talked about the basics of
paper here i’m just going to start drawing a graph remember graphs are nodes and edges where
the nodes are like little t-type data structures that can hold a specific type of value um so i’m
going to say our our nodes hold integers um i think i made that one too small that’s okay
and the edges uh could have weights or maybe not weights at all depending on if you have
a weighted or an unweighted graph so i’m just going to start duplicating my nodes a little bit
going to make a random graph. I need to probably change these values. Technically your graphs
should support duplicate values in the nodes and also the weights, but I don’t want to because
it’s easier to talk about the graph when all the values are distinct. So for starters, we have a
bunch of nodes and they’re not really connected to each other. Is this a valid graph? Yeah it is.
It’s just not a connected graph. So the terminology that we’re going to use for
undirected graphs meaning the edges don’t have direction is going to be connected or not you
know i usually just say a not connected graph or a disconnected graph so just basically like
connected or not connected okay so this is a not connected graph i’m going to say not connected
not cinnamon i’m thinking about food as usual
connected graph why is it not a connected graph well to define what does it mean to be a connected
graph it just means that every single node can find a path to every single other node
in an undirected graph so we can just double check this real fast we can say you know can
node number two find a path to uh you know let me put a question here let’s say we’re going to check
you should be checking all the nodes one by one by one to see if if the node in particular can
first node that can’t do it means the whole graph is not considered connected so you know two it
can’t reach one so that means it’s not a connected graph so this is not a connected graph because one
or more nodes violate the rule of you have to be able to reach every single other node okay so that
means if we want a connected graph we probably just have to start adding edges so I’m going to
go ahead and uh let me let me write the word connected here and then I can like either circle
cross it out. So right now we have no, this is not a connected graph. I’m going to start adding
edges. We’re going to stick with an undirected graph for now. So I’m going to connect two and one
and two and nine, maybe one and 13. Actually, you know what? I’m going to erase this edge
and maybe connect these over here. And the thing is, this is a valid graph that you’re looking at.
it’s just not a connected graph.
Some other terminology I didn’t mention in other videos
is that we can have subgraphs.
We have like a subgraph here and another subgraph here.
Those are basically just two different portions of the same graph
that appear to be connected within themselves.
So those are subgraphs.
You can probably tell right away that this is not a connected graph.
You can double check to be sure.
You know, it’s good to do things the hard way
so you don’t get the wrong answer
when you’re really trying to figure something out.
So let’s look at two.
So let’s look at two. Can two reach one? Yes. So that’s good. Can two reach nine? Yeah,
it just hops to one and then hops to nine. So two can reach one and also nine. That’s good.
Can two reach three? Nope. So this is still not a connected graph.
Okay, I’m going to add one more edge. And then we’ll just check again.
Where do you think I’m going to do it? Maybe if I add, I’ll add a funky edge going from 13 to like
to like nine or something just so it feels a little bit more awkward okay let’s check one by
one by one let me actually get rid of this edge on the previous slide so we can still say that’s
not connected let’s check one by one by one every node must be able to reach every single other
node so I’m gonna look at two and I’m gonna say all right two can it reach one yes can it reach
to nine. So that’s good. Can it reach three? Yeah, it can go from two to one to nine to 13
to three, and then it can reach three. And because we just saw that it went through 13 to reach three,
that means two can reach every single other node. This is going to be more important as a double
check when we have directed graphs in a second. So two is good. So the next thing you want to do is
the next thing you want to do is just move on to some other node and do the exact same process you
know can can nine reach a one yes okay it can reach a one can it reach a two yeah it goes through
the one can it reach the 13 yep can it reach the three yep okay so we just check every single
destination node starting at the node nine but here’s a little bit of a shortcut try to find a
node that is right next to a node that you know can reach everything and if the node in question
that previously connected node, vertex,
then we know that that node in particular is also connected.
So what I’m saying is the one,
instead of checking every single other node in the graph,
which might be really hard
if we have a whole bunch of nodes in our graph,
we’ll just ask, can the one reach the two?
Because if it can, the two can reach everything.
So that means the one actually can reach everything as well.
So the one can reach the two.
So the one is connected to everything.
the three, the three can reach the one and the one can reach everything. I’m doing things the
hard way on purpose just to prove a point. So the three can reach everything. The 13 can reach the
three in one hop. So the 13 can reach everything. The nine, it can reach the one and it can reach
the 13 in one hop. So the nine can also actually reach everything. So that means this is indeed a
the next thing that we’re going to do is add direction to our graph you know we could do like
more examples maybe leave a comment if you want me to do some super extra complicated examples for
just a undirected and connected graph i’m ignoring weight by the way because it doesn’t really matter
for these purposes so let’s upgrade our graph so uh maybe i should put a question mark here
that would have been a good idea we’re just asking you know is it connected or not
And I’m just going to start adding direction to every single edge.
Let’s see if I’m following my notes.
Single node, subgraphs, right?
Well, it wasn’t connected at first and then we started adding.
Okay, so that’s basically okay.
Let’s add direction to every single edge.
So every single edge has to have a direction
or every single edge has to have no direction.
You can’t really mix and match.
So I’m just going to go through every single edge and add a direction like this.
and you know to be fair I think I’ve said this in my other videos an undirected edge is kind of the
same thing as a directed edge going in or two directed edges going in both directions so this
3 and 13 what’s going on with my computer hello this 3 and 13 edge it would have kind of been the
same as just having two edges going in opposite directions so maybe I’ll just do that right now
for this huge weird edge I’m just going to put like an arrow over here instead of totally redrawing
Then I double check that every single edge has a direction so that I have a valid graph.
And now I can ask, is this connected or not?
Actually, when it comes to a directed graph, you don’t really have connected or not anymore.
You have strongly connected versus weakly connected.
Maybe I should just separate these words and then just kind of like move them.
So let’s get rid of this.
to this save this over here move it down so what am i talking about um well first let me remove an
edge real quick i’ll remove this edge right here so now we have two sub graphs in this graph you
can tell for sure if this was an undirected graph it would not be connected but now that we’re
dealing with direction we have to ask is it strongly connected versus weakly so what does
can every node reach every other node if you obey the direction of the edges so that’s clearly not
true there’s no edge at all that even connects this one and nine so it’s definitely not strongly
connected weakly connected on the other hand means if you temporarily ignore the direction
of the edges then could you consider the graph connected so if we pretended that there were no
arrows here would we think that it’s a connected graph if the answer is yes then it’s at least a
So this is not weakly connected because if this was an undirected graph, it’s not even connected at all.
So that sucks.
I’m going to go ahead and add another edge here.
So I’m going to add an edge from 2 to 9.
So the first thing is, oh, sorry, I have to add another edge.
Let me do from 1 to 13 for fun.
So now the first thing is, let’s check to see if this is a strongly connected graph.
node is unreachable by any other node so this is definitely not strongly
connected because all the other nodes would be would have to be able to reach
too alright so first thing you could do just to very quickly check is just look
at every single node and ask is it reachable you know by anything and then
after that you can do things the hard way so it’s not strongly connected what
about weakly connected if we ignore the direction of the graph sorry if we
then yeah, we could reach every single node from every other node. Let’s just double check that
real fast. I’m going to say, you know, the two node, if we’re ignoring direction, can it reach
the one? Yes. Can it reach the 13? Yes. The three? Yes. Can it reach the nine? Yes. So that means the
two node is sort of like weakly connected to every other node in the graph. Do the same thing for the
one node. Previously, we just said, you know, check everything one by one or use a shortcut.
one by one or use a shortcut. So I’m going to use the shortcut. The one node, if we ignore direction
can reach the two nodes. So I’m going to say the one is weakly connected, at least everything else.
I’m not even going to check to see if it’s strongly connected to everything else. I think the answer
is no, but we do the same thing for the 13. The 13 can reach the one pretty fast. The three can
reach the 13. The nine can reach the two. So every single node can weakly reach. That’s not an
a weakly connected graph. Okay, cool. How can we make this a strongly connected graph? Well,
we just have to add a bunch of edges. So that’s what I’m going to do. I’m going to kind of like
look at what is missing here. So we’ll ask the two, can the two reach and let’s obey the direction
of the edges again. Can the two reach the one? Yes. Can the two reach the 13? Yes. Can it reach
Yes, so that means right now the two is strongly connected to everything else.
So we’re on track for a strongly connected graph.
We then look at the one node and we realize that the one node,
it can reach the 13 and the three and it can also reach the nine,
but it can’t reach the two.
That’s one thing that was blocking us last time from saying strongly connected.
So we just have to add another edge if we want this to be a strongly connected graph.
We have to figure out how can we get the one to reach the two.
the 2 we can go through something if we want to that’s fine we can also just
write an edge that just goes back to the 2 but that’s I don’t know that’s kind of
boring I’m gonna make an edge that goes from 1 to 9 and then I’m gonna make an
edge that goes from 9 to 2 so looking at the 1 node it can now reach the 2 if we
go through the 9 so that’s good can the 1 reach the 9 yes can the 1 reach the 13
three yes okay so the one node can now reach every single other node so now we’re a little bit more
on track for a strongly connected graph look at the 13 node can it reach the one node um actually
yes if we go from 13 to 9 and then 2 and then 1 we can reach the one node since we know the one
node is connected to everything else we can now say that the 13 node is connected to everything
13 so i’ll say three is connected to everything the nine node can reach the two node which is
connected to everything so that means the nine node is also connected to everything and at this
point we now have a strongly connected graph it’s not weakly connected it’s stronger than that
any questions um so let’s see we added a bunch of uh edges i think maybe this is actually all we
need to do for this particular video because we’re just going to talk about connectedness
going to talk about connectedness about 15 minutes not too bad all right so i think i’m
going to leave it here drop a comment if you want to do way more complicated examples if you want to
provide me a sample graph that’s awful and i could just i don’t know in the sometime in the future i
could record a video about it um or just let me know your thoughts thank you so much for watching
this video i hope you had a little bit of fun and i hope you learned a little bit of stuff i’m outie
Patowdy.
Alright, let’s see.
I’m going to do this.
Whoa. Can you see that guy in the background?
Oh, shoot.
I’m just kidding.
I set that as the screensaver.
Hey, everybody.
Thanks for watching this video again from the bottom of my heart.
I really appreciate it.
I do hope you did learn something and have some fun.
If you could do me a please, a small little favor,
please subscribe and follow this channel or these videos or whatever it is you do on the current
social media website that you’re looking at right now. It would really mean the world to me and it’ll
help make more videos and grow this community. So we’ll be able to do more videos, longer videos,
better videos, or just I’ll be able to keep making videos in general. So please do me a kindness
and subscribe. You know, sometimes I’m sleeping in the middle of the night and I just wake up
or followed. It just wakes me up and I get filled with joy. That’s exactly what happens every single
time. So you could do it as a nice favor to me or you could you could troll me if you want to just
wake me up in the middle of the night. Just subscribe and then I’ll just wake up. I promise
that’s what will happen. Also if you look at the middle of the screen right now you should see a
QR code which you can scan in order to go to the website which I think is also named somewhere at
the bottom of this video and it’ll take you to my main website where you can just kind of like see
videos i published and the services and tutorials and things that i offer and all that good stuff
and uh if you have a suggestion for uh uh clarifications or errata or just future videos
that you want to see please leave a comment or if you just want to say hey what’s up what’s going on
you know just send me a comment whatever i also wake up for those in the middle of the night i get
i wake up in a cold sweat and i’m like it would really it really mean the world to me i would
it so again thank you so much for watching this video and enjoy the cool
music as as I fade into the darkness which is coming for us all
Thank you.
so
I’m going to go ahead and get started.
so
Yeah, I think I’m good.
Hello there.
Let’s talk about whether a graph is connected or not,
or maybe whether it’s strongly connected or weakly connected or not connected at all.
You never know.
