Graph Isomorphism, Degree, Graph Score

Loading...

En provenance du cours de Shanghai Jiao Tong University

Discrete Mathematics

94 notes

Shanghai Jiao Tong University

Discrete Mathematics

94 notes

Discrete mathematics forms the mathematical foundation of computer and information science. It is also a fascinating subject in itself. Learners will become familiar with a broad range of mathematical objects like sets, functions, relations, graphs, that are omnipresent in computer science. Perhaps more importantly, they will reach a certain level of mathematical maturity - being able to understand formal statements and their proofs; coming up with rigorous proofs themselves; and coming up with interesting results. This course attempts to be rigorous without being overly formal. This means, for every concept we introduce we will show at least one interesting and non-trivial result and give a full proof. However, we will do so without too much formal notation, employing examples and figures whenever possible. The main topics of this course are (1) sets, functions, relations, (2) enumerative combinatorics, (3) graph theory, (4) network flow and matchings. It does not cover modular arithmetic, algebra, and logic, since these topics have a slightly different flavor and because there are already several courses on Coursera specifically on these topics.

À partir de la leçon

Introduction to Graph Theory

Graphs are arguably the most important object in discrete mathematics. A huge number of problems from computer science and combinatorics can be modelled in the language of graphs. This module introduces the basic notions of graph theory - graphs, cycles, paths, degree, isomorphism.

Graph Isomorphism, Degree, Graph Score13:29

Rencontrer les enseignants

Dominik Scheder
Assistant Professor
The Department of Computer Science and Engineering

[MUSIC]

[SOUND]

Hello everybody,

welcome to our online course on discrete mathematics and

to our second lecture on graph theory.

Today, the first topic I want to talk about is the following question.

When are two graphs the same?

This may sound like a stupid question but actually it's not.

For example, this graph and this graph.

They don't look the same, but let's take a close look.

Are they the same?

Well, let's see our mathematical definition of a graph.

What is the vertex set?

Well, the vertex set is a, b, c, d.

And you can see all edges are there.

So the edge set is V 2 and in the graph on

the right hand side, it's just the same.

It's the same vertex set and it's the same edge set, so yes,

we conclude these two graphs are the same.

They are just drawn differently.

The same graph.

Okay, how about these two graphs?

Certainly, they don't look like each other, but if you think,

if you look very closely, in some way, they are the same.

But not quite.

Because here.

What is the vertex set?

The vertex set is the set of numbers from 0 up to 7 and

here, the vertex set is the power set of 1, 2, 3.

So obviously, already the vertex sets are not the same.

So mathematically speaking, it's not the same graph.

So far, so easy.

Again, these two graphs, you can see are the same but

this graph is different because for example here,

you have an edge from a to c but in the last graph, you don't.

So we see these graphs are the same.

But these graphs are not the same.

But in some way, all these graphs look the same.

The only way they differ is the names we gave to the vertices.

But if for a moment we ignore the names and we just want to look at the structure

of a graph, we could argue in some way, they are all the same.

And this way of thinking in some way, they are all the same

can be made precise mathematically, and that's what we are going to do next.

So now, we'll give a precise mathematical definition,

what it means to look the same.

That's called a graph isomorphism.

So take your time to work through this definition.

What I now want to do, I want to illustrate this definition at an example.

So remember you can always hit pause if I'm going too fast and

really reach for my slides.

But I don't have to sit there and watch you doing this.

Okay, so I proceed and show a graph isomorphism at this example.

So here, we have two graphs as we have seen there,

not the same, but here is an isomorphism.

So I take the vertex in the left graph and

I map it to the vertex a in the right graph.

So it's basically, something like this.

And then I take the vertex c and

I map it to d.

I take b and I map it to c.

And I take d and I map it to b.

So what you have here is we have a graph (V, E), and

we have here a different graph on the same vertex set, (V, E prime).

And this thing here, well, this is a function from V to V.

It's bijective and

it satisfies all the conditions of a graph isomorphism we defined on the last slide.

So this is an isomorphism.

That second little bit more complicated example,

this cube on the left-hand side and

this double square on the right hand side, what can we do here?

Well, I'll put for example start and say well,

this vertex should map to this vertex.

So, we take the empty set and we map it to the vertex 0.

Okay, so how should we continue?

What should we do with the 1?

Well, one thing is, it should be mapped to a neighbor of zero,

because it's a neighbor of the empty set in the graph to the left.

So now we have a choice between 1, 2, and 4.

Now we have to make a choice.

Maybe we made the mistake.

So let's say we map the set 1 to the vertex 4.

So let's write that down.

This is the set 1 and

let's map the set 3 to the vertex 2.

In the other neighbor, the last neighbor which is this here.

We should now map to the last neighbor of 0 which is 1, there you go.

Now you can see whether you can finish the isomorphism.

Figure out how you should map the vertices on the left to the vertices of

the right to get an isomorphism.

All right.

Do this now, when you're done, come back to me.

The concept of isomorphism is important because

it allows us to extract from the actual representation of a graph,

either how the vertices are named or how we draw the graph in the plane.

So for example, you can see this graph, and this graph, they don't look alike, but

they are isomorphic as we have seen.

Also, this graph is isomorphic.

I encourage you to proof this.

And also this graph.

So these are four different ways to draw the same, not the same,

but isomorphic graphs into the planes.

So maybe take your time and

really figure out the isomorphisms between these four graphs.

That's it about isomorphism for today.

The next thing is I want to talk about the degree of a vertex.

If you have a graph such like this, the degree of a vertex is simply

the number of edges, this vertex participates in.

So formally, the degree of

a vertex is the number of

edges in E such that u is in e.

That's the degree of a vertex.

So we have seen this graph,

before that's the kinesic graph, 5, 2,

and here you can see the degree of every vertex is 3.

And such a graph, we call the 3-regular.

And in general, d-regular will just mean that the degree of a vertex,

of every vertex is d.

So regular graphs are also very important.

Here is another d-regular graph.

3-regular.

This is the graph we have already seen a couple of times.

The most fundamental fact about the degrees

of the vertices in a graph is a so-called handshaking lemma.

I'll let you figure out why it's called the handshaking lemma.

So it says if you add up the degrees of the vertices,

you get twice the number of edges.

Yeah, you can try to come up with a proof yourself.

If you're too lazy for that or too impatient, I will show you one,

so here is an example graph.

And because it's Christmas time right now when this video is being shot,

I want to give Christmas cookies to the edges, so

every edge gets two Christmas cookies and I place them at the two ends of each edge.

In reality, Christmas cookies are not really red.

But who cares?

Good, so every edge has received two Christmas cookies.

So I have distributed a total amount of 2 E Christmas cookies.

Another bird had just come and they eat up the Christmas cookies.

And every bird eats up all the Christmas cookies that are placed next to it.

So vertex u eats deg(u) cookies.

And you see in the end, all the cookies are eaten up, so

how many cookies are eaten?

Well, this is just the sum of all degrees.

So the sum of all degrees equals to E.

All right?

That's the handshaking lemma.

Well, the handshaking lemma has a very innocent corollary

which has surprisingly powerful applications.

Maybe in six lectures from now, we will see two such very nice applications.

So the corollary states the number of odd-degree vertices is even.

Let's see in this graph, this vertex has odd-degree and this has odd-degree.

So here we have two odd-degree vertices which is an even number.

So how do you prove this corollary while you just take this equation and

take it modulo 2.

So what you get then.

The right-hand side is clearly 0.

We see that 0 is congruent modulo 2 to the sum of all degrees.

And an even-degree is congruent modulo 0, and an odd-degree is congruent to 1.

So this is congruent to the number of odd-degree vertices.

Odd-degree vertices.

That's the proof.

Right?

Last topic for today, the so-called score of a graph.

The score of a graph is basically just a sequence

of numbers that describes the degrees of the vertices.

So here I have a graph G and the score of G would

simply be (1, 1, 2, 2, 3, 3).

So we take the degree of every vertex, this gives us the sequence of integers,

we sort them from smallest to largest, this is the score of a graph.

Now, the interesting question is which number sequences can

appear as the score of a graph?

Let see some examples.

Can a graph have the following score?

The answer is obviously no.

You see, the graph has only two vertices, but here, we have a 7.

So there are not enough vertices that could be neighbors of this vertex.

This is clearly impossible.

How about this?

This is less obvious, but if you look at it, we have three vertices of odd-degree,

but we have just learned the number of odd-degree vertices must be even.

So this is also impossible.

So now, the homework for you is the following,

Find other impossible sequences.

And of course, you should look for none obvious sequences.

You should look for sequences that are impossible, but

it's really not that obvious that they're impossible.

The other is, if two graphs are isomorphic then they have the same score.

I should have introduced this earlier.

This symbol here, just means G and H are isomorphic.

So this equality sign with a tilde above it And

your last homework is find G and H,

such that they have the same score.

But they are not isomorphic All right, good luck with this homework.

In the next lesson, we'll actually see a characterization of sequences

that can appear as a square of a graph.

That's what we will do next time.

Thanks for today.

[MUSIC]

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play