AIHL 3.14 Introduction to Graph Theory | Free Mathematics Applications & Interpretation (AI) Video | RevisionDojo
Free video lessonIB · Mathematics Applications & Interpretation (AI)
AIHL 3.14 Introduction to Graph Theory
Learn AIHL 3.14 Introduction to Graph Theory in this free IB Mathematics Applications & Interpretation (AI) video lesson for AHL 3.14—Graph theory.
Learn AIHL 3.14 Introduction to Graph Theory in this free IB Mathematics Applications & Interpretation (AI) video lesson for AHL 3.14—Graph theory.
The video introduces Graph Theory, starting with the historical context of the Seven Bridges of Konigsberg problem, which Euler attempted to solve. This problem led to the development of graph theory, where graphs consist of vertices (points) and edges (connections), illustrating relationships between objects.
Key concepts covered include:
Vertices and edges: Vertices represent points, while edges represent connections between them.
Types of graphs:
Simple graphs (no loops or multiple edges)
Complete graphs (every pair of distinct vertices connected)
Weighted graphs (edges assigned numerical values)
Directed graphs (edges have a direction)
Connected graphs (paths exist between any two vertices)
Trees (connected graphs with no cycles)
The video emphasizes the importance of understanding these concepts as they form the foundation for more advanced topics in graph theory.
00:00Hi guys, so in this
00:02video I'm going to just
00:03introduce you to Graph Theory
00:05and go through some of
00:07
the basics of what a
00:08graph is. I'm going to
00:09start with a story of
00:12where it all came from
00:13and it's of course the
00:15man himself, Euler, who invented
00:18it and he invented it.
00:19He came up with it
00:20whilst trying to solve this
00:23problem and it's called the
00:24Seven Bridges of Konigsberg problem.
00:28And basically what the problem
00:29is is to This was
00:33a town that I think
00:34doesn't exist anymore, but then
00:36this happened I think 1736
00:39was when when art released
00:42his paper anyway about it
00:43But anyway, he was working
00:44on this the problem was
00:46he wanted to cross each
00:49bridge once and Without our
00:55exact
00:56be once. So pass every
00:58bridge without going back on
01:00the same bridge. So for
01:01example, you start it here,
01:03you can go over here,
01:06back again, over here, along
01:09here. And then as soon
01:11as you get to there,
01:12you've got a problem because
01:13you have to cross one
01:14of these bridges again. Or
01:16even if you went up
01:16this way, you've the same
01:18kind of problem. Maybe you
01:19can start in the middle,
01:21you go along here, up
01:22here,
01:24down here, now I've got
01:25a problem. I can't go
01:28up here. Anyway, cut a
01:30long story short, or figure
01:31it out that it cannot
01:33be done. And that was
01:35kind of how graph theory
01:36started. And it became to
01:39be really, really useful. And
01:41it's a very, very important
01:42part of mathematics, especially now
01:44with in computing, it's very,
01:46very important in computers and
01:49networking. So what it is
01:51is what we look at
01:52is it is a graph,
01:54this is a graph here,
01:55let me actually draw this
01:57problem in graph form. So
02:00we have these things called
02:02vertices. So imagine each kind
02:06of island here is a
02:07vertex. So this is a
02:08vertex. This middle one is
02:10a vertex. This one over
02:13here is a vertex. And
02:16say this is a vertex
02:17here, this one. And these
02:20These are connected by bridges.
02:24So this one here is
02:25connected to this twice. So
02:27he's connected here. And he's
02:30connected like this. And this
02:33guy is connected like this.
02:36So the middle one is
02:37connected to here also twice.
02:41I don't notice it doesn't
02:42really matter how I draw
02:44these lines to come straight.
02:45It can be curved, whatever.
02:47This guy,
02:48connected to him once like
02:50this. He is connected to
02:53him once and he's connected
02:54to him once. So this
02:56is basically this seven bridges
03:02of coning's birth problem in
03:04graph form. So these are
03:07vertices and these black lines
03:10are called edges. So in
03:11this case the bridges are
03:13the edges.
03:16Okay, so what what it's
03:19doing is it's looking at
03:21the relationship between some object
03:23so these can be anything
03:25in this case. It's It's
03:27like a piece of land,
03:28but it might be a
03:29computer so a computer is
03:32connected to other computers. So
03:34it looks at the relationship
03:35of the pairs It's the
03:37relationship of the computers in
03:39pairs. So this is a
03:40relationship to him. This guy's
03:41relationship to him. His relationship
03:42to him. His relationship to
03:44him. His relationship to him.
03:44et cetera, and I'll also
03:45look at his relationship to
03:47him through him or whatever,
03:49like, whatever way you want
03:51to do it. Okay, so
03:52this is a graph. I
03:56want to go through all
03:57the kind of technical terms
03:59here, and then I want
04:00to talk about the different
04:03types of graphs that you
04:04will be coming across as
04:08I go through this whole
04:10kind of unit. Okay.
04:12So as I said, these
04:14the blue points dots objects
04:17whatever you want to call
04:18them are called vertices or
04:21singular vertex. So this is
04:23a vertex. The black lines
04:27that join the vertices are
04:28called edges. So this is
04:29an edge. These are adjacent
04:32edges because they're beside each
04:34other. These are adjacent vertices
04:36because they're beside each other
04:37adjacent means beside each other.
04:39And this is a loop.
04:40So a loop is an
04:41edge that leaves a vertex
04:44and actually comes back to
04:46the same vertex. So you're
04:47going to come across that
04:49from time to time. It
04:51might in this situation it
04:52would be a bridge that
04:54actually goes nowhere, just leaves
04:56the sign that comes back
04:57to itself. Obviously that would
04:58make much sense in that
05:00particular situation. The order of
05:03a graph is the number
05:05of vertices. So the order
05:06of this graph is 1,
05:072, 3, 4, 5, 6.
05:08This is a graph of
05:10order six. The size of
05:11the graph is the number
05:12of edges. So this guy
05:14is one, two, three, four,
05:17five, six, seven, eight, nine.
05:19I remember this is the
05:20loop is an edge. So
05:21that the size of this
05:21graph is the graph of
05:23size nine. Okay. Next thing
05:28I want to look at
05:29are some types of graphs.
05:32First the simple graph. This
05:34is a graph that contains
05:36no loop
05:36are multiple edges. So this
05:40that we had here, these
05:41are multiple edges joining these
05:43two vertices. There's two edges
05:45joining the same two vertices.
05:48Here I have no multiple
05:50edges, there's just one edge
05:51for each pair and there's
05:54no loops. So it's a
05:55simple graph. A complete graph,
05:58a complete graph is a
05:59simple graph in which every
06:00pair of distinct vertices is
06:02connected by a unique edge.
06:03So basically each of
06:04vertex is connected to all
06:07the other vertices directly. So
06:09he's connected to him. There's
06:11an edge to him. There's
06:13an edge to him. And
06:13you can do that with
06:14all the other vertices. Often
06:17you might see guys it's
06:18written at k5 is the
06:21complete graph with five vertices.
06:25Now in an exam question,
06:26I'm sure they would actually
06:27define that for you, but
06:28it's worth knowing they're coming
06:29across that. Like k4, k4,
06:33or would be the complete
06:35graph with four vertices. And
06:37you could probably draw that
06:38yourself pretty easily. And it's
06:42worth noting this isn't in
06:46the formula book or anything,
06:47but it may. You may
06:48easily come across it. It's
06:50worth noting that kn has
06:52n times n minus 1
06:54over two edges. The reason
06:56for that is if you
06:58think about it, each vertex
07:01is connected. So in this
07:04graph there's five vertices. So
07:05each of the five is
07:06connected to the other four.
07:08So he's connected to four.
07:09So if this four edge
07:10is coming from him, this
07:11four edge is going from
07:12him, this four edge is
07:13coming from him, four from
07:14him, four from him. So
07:15it's five times four, which
07:17is 20, but you have
07:19to divide by two because
07:20you're double counting. If the
07:23edge that connects him to
07:26him, you count it twice
07:28because you
07:29counted it when you connected
07:30him to him but it's
07:31the same edge. So that's
07:33where you divide by two.
07:34In this case you have
07:35five, because n is five,
07:37five times four and minus
07:39one is 20, 20 divided
07:40by two is 10. So
07:41this is 10 edges, one,
07:42two, three, four, five, six,
07:45seven, eight, nine, 10, 10
07:47edges. That's a complete graph.
07:51Next one, a weighted graph.
07:53It's a graph in which
07:54each edge is given a
07:55numerical value. So you'll see
07:57this
07:57quite often there's a numerical
07:58value assigned to the edge.
08:02Now these could mean lots
08:04of things in the IB.
08:07They say in the guide
08:08just that these are either
08:09going to be a cost
08:10so that might be $43
08:12to join A to be
08:14or to get a taxi
08:15from town A to town
08:17B or a time so
08:20it might be 43 minutes
08:21to get from A to
08:22B or a distance.
08:25So, I did a 43
08:27cm joining a computer 8
08:30computer 8, whatever the situation
08:32is. Okay, and obviously E
08:36to C is 55, E
08:37to D is 20. It's
08:39pretty clear that these are
08:41weighted edges, it's a weighted
08:44graph. A directed graph, so
08:48a graph where each edge
08:50has a direction, so clearly
08:52you can see here 8,
08:53A goes to B, there's
08:54an arrow A to B,
08:56but B doesn't go back
08:57to A. So you can
08:58go from A to B,
08:58we can't go back from
09:00B to A. Similarly, you
09:01can go from B to
09:05C, and C to E
09:07to D, but once you
09:09get to D, you're stuck
09:10because you can't get out
09:11of D. There's something called
09:13the N degree and the
09:15out degree. So the degree
09:20is
09:21The in degree here is
09:231. Now maybe I actually,
09:26I just realized I haven't
09:27mentioned the degree. Yeah, I
09:31should have said here the
09:32degree of the degree of
09:34the vertex. So here the
09:36degree of the degree of
09:41the degree of the vertex
09:44is the number of edges.
09:46The number of edges attached
09:49That's two, that vertex, so
09:51one, two, three. So the
09:52degree of vertex is three.
09:55The degree of this vertex
09:56is two. The degree of
09:57this is, well, the degree
09:59of this vertex is one,
10:00two, three, four because of
10:01the loop. And actually, sorry,
10:08be careful. The degree of
10:10the degree of this vertex
10:12is actually five because one,
10:15two, three, four, five, you
10:16have to count.
10:17If there's a loop you
10:18have to count this one
10:20because it's attached here if
10:24you like and then it's
10:25also attached here. So the
10:26degree of this is 5.
10:28So the degree of this
10:29is 3. 2, the degree
10:30of this is 5. 3,
10:324 and 1. But the
10:38n degree is just the
10:39number of edges coming into
10:42that vertex. So in this
10:43case it's 1. The out
10:44degree is 2 because
10:45this two edges leaving E,
10:49I feel like one to
10:50A, I want to D,
10:51in degree and out degree.
10:55Okay, last few. A connected
10:59graph is an undirected graph
11:01in which there is a
11:02path from any vertex to
11:04any other vertex in the
11:05graph. Otherwise, it is disconnected.
11:07So basically, you can get
11:09from any vertex to any
11:11other vertex. So this guy,
11:12you can go along here
11:13and up there.
11:13You can go from here
11:15to here. You can pick
11:17any two and you can
11:18get from there. There is
11:19a path, this is actually
11:21a technical term that will
11:22come across in a later
11:23lesson, but a path is
11:24somewhere you can basically, you
11:26can, if you want to
11:27think about it as walking
11:28along these lines, so you
11:30can walk along from here
11:31to here and you can
11:32get from any one, any
11:34vertex to any other vertex.
11:36But this guy is disconnected
11:37because you can't get from
11:39here, you can't get from
11:40him to him.
11:41You have to jump across,
11:43which is not allowed. So
11:45this is a disconnected graph.
11:47A strongly connected graph is
11:50a directed graph, so that's
11:51the one with the arrows,
11:52in which there is a
11:53path from any vertex to
11:55any other vertex in the
11:56graph, otherwise it is not
11:57strongly connected. So here, again,
12:04pick your vertex and pick
12:07your other vertex, and you
12:07can get, I've designed it,
12:09So it's strongly connected. Like
12:11for example, if we're here,
12:12we can get to here.
12:13We can go there, there,
12:16there. If we're here, we
12:17can get to here. So
12:18there are there. You may
12:21think you're stuck if you're
12:22in this vertex here, but
12:23actually this edge goes both
12:28ways. So you can get
12:29from here to here by
12:30going along there up there,
12:32up there, et cetera. So
12:33you can get from any
12:34vertex to any other vertex.
12:36This guy, this
12:37is not strongly connected because
12:41let's try and find where
12:43we get stuck. Okay, here
12:46we cannot get to this
12:48vertex. If we start here,
12:50we can go along, we
12:52can go up, we can
12:53go up, but then we're
12:54stuck, we cannot get to
12:55him and then down here
12:56we cannot get him. So
12:57it's not a strongly connected
12:59graph. If I got rid
13:00of all those arrows, it
13:01would be a connected graph,
13:03but because there is
13:06Because it is a directed
13:07graph, it is not strongly
13:10connected. I know that sounds
13:12strange Okay, last two I
13:15believe a Subgraph pretty clear
13:19it's a graph formed from
13:20a subset of the vertices
13:21and edges of another graph
13:22So for example, this is
13:24a subset of this graph
13:26because here I have Well,
13:29here's a graph a b
13:30c d e, but this
13:32c d e is
13:34is the same as this
13:36CDE. The vertices are the
13:40same, the edges are the
13:42same, and they're also going
13:45in the same direction. They
13:46have to be going in
13:47the same direction for it
13:48to be a subset of
13:51the graph. Otherwise, it is
13:52not a subset. Now note,
13:54it doesn't really matter, guys,
13:56how you draw the graph.
13:58Like I could put, I
13:59could move A down here,
14:01as long as there's
14:02but the edges are the
14:04same, and they're still going
14:05the same direction. It's still
14:07the exact same graph. Finally,
14:10a tree, you might notice
14:13this looks a bit like,
14:15if you remember, if you're
14:17a tree diagram from probability,
14:20not related, but it does
14:21look a bit like this.
14:22So an under -acted graph
14:24in which any two vertices
14:25are connected by exactly one
14:28path or a connected
14:30graph that contains no cycle.
14:33So essentially, there's only one
14:34way to get from one
14:36vertex to another. So if
14:39you want to get from
14:39him to him, you have
14:40to go here, then here,
14:42then here. Or you have
14:42to go from here to
14:43here. Or if you're down
14:45here, you have to go,
14:46if you want to get
14:46from him to him, you
14:47have to go there, then
14:48there, then there. This is
14:52kind of like another definition.
14:53It says, or a connected
14:54graph that contains no cycles.
14:56So cycle, again, you're going
14:57to come across
14:58this in a later lesson,
14:59but imagine it's like this.
15:02This graph now contains a
15:04cycle because you can go
15:05kind of go around it.
15:06So there will be two
15:07ways to get to this
15:09graph. You could go there
15:10or to get to this
15:11vertex. You could go here
15:12and here or you could
15:13go here, here and here.
15:16So this is no longer
15:17a tree, but now it's
15:20a tree. So this is
15:20a tree and this is
15:22a tree. I wanted to
15:23put the two that they
15:24look. They don't always look
15:26like this. In fact, I
15:27would say this is probably
15:28the more common tree that
15:31looks something like this. Okay,
15:33that's it. That's the introduction
15:35to Graph3. Hope that makes
15:37sense. Certainly, there's no way
15:40you would remember everything I've
15:41just said there, but you'll
15:43be coming across all those
15:44different terminology and over the
15:49next few lessons. And this
15:53is a fun topic, guys.
15:54I hope that hasn't scared
15:56you. I'll put you off.
15:58Okay, see you in the
15:59next lesson.
About this video
Video transcript
Keep learning for free
Create a RevisionDojo account to save videos and track your study progress.