Graph Theory Flashcards
This deck is an introduction to graph theory.
What is a graph?
Object consisting of 2 sets called Vertex set and Edge set
What is Vertex set?
Finite nonempty set
Example:
{P. Q, R, S, T, U}
What is Edge set?
Pair of vertex elements. It can be empty.
{{P, Q}, {P, R}, {Q, R}, {S, U}}
Vertices and Edges
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
What are adjacent vertices
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.
What are incident edges
The edge {X, Y} is incident to each X and Y and each of X and Y is incident to {X, Y}
What are adjacent Edges
Two edges incident to the same vertex.
What is Isolated Vertex?
A vertex incident to no edge.
What are graph diagrams?
Representation of a graph. The vertices are represented by heavy dots. Vertex adjacency is represented by connecting the corresponding dots.
What is graph equality?
Two graphs are equal if the have equal vertex sets and equal edge sets.
What is graph diagram equality?
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}}
What are undirected graphs?
The edges of a graph are undirected.
{A, B} = {B, A}
What are Cyclic graphs?
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
\_\_\_\_\_\_\_\_\_ | | | | | | ------------------
What are Complete graphs?
Graph having all possible edges. Denoted by Kv
What are Null graphs?
Graphs having vertex set but not an edge set. Denoted by N
What is utility graph?
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.
What is the formula to find how many edges a utility graph has?
e = 1/2v(v-1)
What is complement of graphs?
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
What are subgraphs?
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.
What are isomorhic graphs?
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}}
What is degree of a vertex?
Number of edges the vertex incident to. In other words how many edges the vertex has.
What properties does isomorphic graph has?
- 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.
What is planar graph?
Graph that can be drawn in a plane surface without the edge crossing.
What is Jordan Curve Theorem
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.
What are the subgraphs of a planar graph?
Subgraphs of a planar graph is a planar graph.
What are supergraphs?
If a graph H is a subgraph of G we say that G is a supergraph of G.
What is graph expansion?
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.
What are the expansions of UG or K5?
Every expansion of UG or K5 is nonplanar.
What are the supergraphs of an expansion of UG or K5?
Every supergraph of an expansion of UG or K5 is nonplanar.
What is Kuratowski Theorem?
Every nonplanar graph is a supergraph of an expansion of UG or K5.
What is a walk in graph?
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
What are the graph walk properties?
- Null graph does not have walks.
- Any sequence of distinct vertices in Kv is a walk.
What are connected and disconnected graphs?
A graph is connected if every pair of vertices is joined by a walk.
What are the known graphs properties regarding connected and disconnected graphs?
- Every cyclic graph is connected
- Every complete graph is connected
- Except for N1 all null graphs are disconnected.
What are polygonal graphs?
A graph is polygonal if it is planar, connected and every edge borders on two different faces.
What are regular graphs?
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.
What are platonic graphs?
A graph is platonic if it is polygonal regular, and all of its faces are bounded by the same number of edges.
What is a colored graph?
A graph has been colored if a color has been assigned to each vertex in such a way that adjacent vertices have different colors.
What is chromatic number of graph?
The chromatic number of a graph is the smallest number of colors with which it can be colored.
Chromatic number is denoted with X.
What is open walk in a graph?
A walk A1, A2, …, An-1, An in a graph is closed if A1 and An is the same vertex and open otherwise.
What is Euler walk?
An euler walk is a walk that uses every edge in the graph exactly ones.
What is even vertex?
A vertex is even if its degree is even.
How to find if there exists a closed euler walk in a graph?
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.
What is odd vertex?
A vertex is odd if its degree is odd.
How to find if there exists an open euler walk in a graph?
If a connected graph has an open euler walk then it has exactly two odd vertices.
What is an open Hamilton walk?
A walk that uses every vertex in the graph exacly once.
What is closed Hamilton walk?
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.
What is a skein?
Object consisting of two dots connected by two or more lines.
What is a multigraph?
If some of the edges of a graph together with their incident vertices are replaced by skeins is called multigraph.
