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