Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Discrete Math > Graph Theory > Flashcards

Graph Theory Flashcards

This deck is an introduction to graph theory.

1
Q

What is a graph?

A

Object consisting of 2 sets called Vertex set and Edge set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is Vertex set?

A

Finite nonempty set

Example:
{P. Q, R, S, T, U}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is Edge set?

A

Pair of vertex elements. It can be empty.

{{P, Q}, {P, R}, {Q, R}, {S, U}}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Vertices and Edges

A

The elements of the vertex set are called vertices and the elements of the edge set are called edges.

v - number of vertices
e - number of edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are adjacent vertices

A

Assume {X, Y} is edge of a graph {X, Y} connects the vertices X and Y together. X and Y are adjacent to one another.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are incident edges

A

The edge {X, Y} is incident to each X and Y and each of X and Y is incident to {X, Y}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are adjacent Edges

A

Two edges incident to the same vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is Isolated Vertex?

A

A vertex incident to no edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are graph diagrams?

A

Representation of a graph. The vertices are represented by heavy dots. Vertex adjacency is represented by connecting the corresponding dots.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is graph equality?

A

Two graphs are equal if the have equal vertex sets and equal edge sets.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is graph diagram equality?

A

Two graph diagrams are equal if they represent equal vertex set and equal edge set.

Example:

{P, Q, R, S, T, U}
{{P, Q}, {P, R}, {Q, R}, {S, U}}

{T, P, R, Q, U, S}
{{Q, R}, {R, P}, {U, S}, {P, Q}}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are undirected graphs?

A

The edges of a graph are undirected.

{A, B} = {B, A}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are Cyclic graphs?

A

Graphs having v>=3 and vertex set {1, 2, 3, … v} and edge set {{1, 2}, {2, 3}, {3, 4}, ….{v, 1}}. They are denoted by Cv

\_\_\_\_\_\_\_\_\_
|                  |
|                  |
|                  |
------------------
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are Complete graphs?

A

Graph having all possible edges. Denoted by Kv

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are Null graphs?

A

Graphs having vertex set but not an edge set. Denoted by N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is utility graph?

A

Graph having vertex set {A, B, C, X, Y, Z} and edge set
{{A, X}, {A, Y}, {A, Z}, {B, X}, {B, Y}, {B, Z}, {C, X}, {C, Y}, {C, Z}}.

Unlike other types of graph Utility Graph is only one. Denoted by UG.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the formula to find how many edges a utility graph has?

A

e = 1/2v(v-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is complement of graphs?

A

Complement of graph G denoted by G’ is a graph with same vertices bu entirely different edges. If two vertices are connected in G they are not connected in G’ and vice versa.

Null graphs and Complete graphs are complementary. For every positive integer v, Nv’ is equal to Kv and Kv’ is equal to Nv

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are subgraphs?

A

A graph H is a subgraph of G when the vertex set of H is a subset of G and the edge set of H is a subset of Gs edge set.
Every graph is a subset of themselves.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are isomorhic graphs?

A

Two graphs are said to be isomorphic if between their vertex set exists one-to-one correspondence. Whenever two corresponding vertices are adjacent to one graph they are adjacent to the other one.

Example:
G = {A, B, C, D} {{A, C}, {A, D}, {C, B}}
H = {1, 2, 3, 4} {{3, 2}, {3, 4}, {2, 1}}

21
Q

What is degree of a vertex?

A

Number of edges the vertex incident to. In other words how many edges the vertex has.

22
Q

What properties does isomorphic graph has?

A
  • An isomorphism is one-to-one correspondence (bijection) of vertices.
  • One-to-one correspondence between edge sets
  • Isomorphic graph’s corresponding vertices has the same degree.
23
Q

What is planar graph?

A

Graph that can be drawn in a plane surface without the edge crossing.

24
Q

What is Jordan Curve Theorem

A

Figure you can draw with a pencil without lifting and crossing edges which have the same starting and finishing point.

This figure divides the rest of the canvas into 2 regions-inside and outside having the figure as their common boundry. If there is a point P in one region and point Q at the other region and a line L joining P with Q it menas that L crosses the figure.

25
Q

What are the subgraphs of a planar graph?

A

Subgraphs of a planar graph is a planar graph.

26
Q

What are supergraphs?

A

If a graph H is a subgraph of G we say that G is a supergraph of G.

27
Q

What is graph expansion?

A

If some new vertices of degree 2 are added to an existing graph’s edge, the resulting graph H is called an expansion of G.

28
Q

What are the expansions of UG or K5?

A

Every expansion of UG or K5 is nonplanar.

29
Q

What are the supergraphs of an expansion of UG or K5?

A

Every supergraph of an expansion of UG or K5 is nonplanar.

30
Q

What is Kuratowski Theorem?

A

Every nonplanar graph is a supergraph of an expansion of UG or K5.

31
Q

What is a walk in graph?

A

Sequence of type A1, A2, A3, …, An of not necessarily distinct vertices in which A1 is joined by an edge to A2, A2 is joined by an edge to A3 … and An-1 is joined by an edge to An.

The walk A1, A2, A3, …, An is said to join A1 and An

32
Q

What are the graph walk properties?

A
  • Null graph does not have walks.

- Any sequence of distinct vertices in Kv is a walk.

33
Q

What are connected and disconnected graphs?

A

A graph is connected if every pair of vertices is joined by a walk.

34
Q

What are the known graphs properties regarding connected and disconnected graphs?

A
  • Every cyclic graph is connected
  • Every complete graph is connected
  • Except for N1 all null graphs are disconnected.
35
Q

What are polygonal graphs?

A

A graph is polygonal if it is planar, connected and every edge borders on two different faces.

36
Q

What are regular graphs?

A

A graph is regular if all the vertices have the same degree.

If the common value of the degrees of a regular graph is the number d, we say that the graph is regular of degree d.

37
Q

What are platonic graphs?

A

A graph is platonic if it is polygonal regular, and all of its faces are bounded by the same number of edges.

38
Q

What is a colored graph?

A

A graph has been colored if a color has been assigned to each vertex in such a way that adjacent vertices have different colors.

39
Q

What is chromatic number of graph?

A

The chromatic number of a graph is the smallest number of colors with which it can be colored.

Chromatic number is denoted with X.

40
Q

What is open walk in a graph?

A

A walk A1, A2, …, An-1, An in a graph is closed if A1 and An is the same vertex and open otherwise.

41
Q

What is Euler walk?

A

An euler walk is a walk that uses every edge in the graph exactly ones.

42
Q

What is even vertex?

A

A vertex is even if its degree is even.

43
Q

How to find if there exists a closed euler walk in a graph?

A

If a connected graph has closed euler walk then every vertex is even.

If a graph is connected and every vertex is even then it has a closed euler walk.

44
Q

What is odd vertex?

A

A vertex is odd if its degree is odd.

45
Q

How to find if there exists an open euler walk in a graph?

A

If a connected graph has an open euler walk then it has exactly two odd vertices.

46
Q

What is an open Hamilton walk?

A

A walk that uses every vertex in the graph exacly once.

47
Q

What is closed Hamilton walk?

A

A closed walk that uses the initial vertex exactly twice and all other vertices in the graph exactly once.

Every graph with a closed Hamilton walk also has an open Hamilton walk.

48
Q

What is a skein?

A

Object consisting of two dots connected by two or more lines.

49
Q

What is a multigraph?

A

If some of the edges of a graph together with their incident vertices are replaced by skeins is called multigraph.

Discrete Math (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions