math 401 test 3 Flashcards
the size of the vertex set |V| is called the ? of G
order
G is a multigraph if
there are some repeated edges {xi, xj} (called a multiple edge) for i=/=j in E
G is a general graph if
we further allow a multigraph to have {xi, xi} (called a loop) in E
how to count the degree of a vertex with a loop
the loop counts twice for degree (but only once for edge)
Σd(vi) from i to n =
2|E|
Handshake problem: prove that the number of people that shake hands an odd number of times is even
Σd(vi) of the odd’s + Σd(vi) of the even’s must be = 2|E|. Since Σd(vi) of the evens will be even, the Σd(vi) of the odds must be even as well
Two general graphs are called isomorphic provided that
|V| = |V’| and |E| = |E’|
Let G be a (general) graph. G’ is a (general) subgraph of G if
V’⊆V and E’⊆E
G’ is a spanning (general) subgraph of G if
V’ = V and E’ ⊆ E
G’ is a (general) subgraph induced by V’ if
any edge of G with both end-vertices in V’ is also an edge of G’
A walk is closed if
you return to the starting vertex
A walk is open if
you do not return to the starting vertex
A trail is
a walk with distinct edges
A closed trail is
a closed walk with distinct edges
A path is
a walk with distinct vertices
A cycle is
a closed walk with distinct vertices
A general graph is called connected provided that, for each pair of vertices x and y, there is
a walk joining x and y
Let G and G’ be two general graphs. Then the following are necessary conditions for G and G’ to be isomorphic
- if G is a graph, so is G’
- G and G’ have the same number of components
- if G has a cycle equal to some length k, so does G’
- if G has an (induced) general subgraph that is a complete graph Km, so does G’
The adjacency matrix is an n x n array such that
the entry aij in row i and column j equals teh number of edges joining xi and xj
An open Eulerian trail is
an open trail which contains each edge of a graph G exactly once
a closed Eulerian trail is
a closed trail which contains each edge of G exactly once
Let G be a connected general graph. G has a closed Eulerian trail if and only if
the degree of each vertex of G is even
Let G be a connected general graph. G has an open Eulerian trail if and only if
G has exactly two vertices of odd degree
Let G be a connected graph and suppose that the number of vertices of G with odd degree is m>0. Then the edges of G can be partitioned into ? trails. It is impossible to partition the edges of G into fewer than ? open trails.
m/2
A Hamiltonian chain is
a chain connecting all vertices of G
A Hamiltonian cycle is a
cycle containing all vertices of G
A connected graph with a ? does not have a Hamiltonian cycle
bridge
Let G be a graph with order n>=3.
a) If the sum of degrees of any two non-adjacent vertices is at least n, then G has a Hamiltonian ?
b) If the sum of degrees of any two non-adjacent vertices is at least n-1, then G has a Hamiltonian ?
a) cycle
b) chain
Let G = (V,E) be a multigraph. G is called bipartite provided the vertex set V can be
partitioned into two subsets X and Y such that each edge of G has one vertex in X and one vertex in Y (X and Y is called a bi-partition of G)
A multigraph is bipartite if and only if
each of its cycles has even length
Let G be a bipartite graph with bi-partition X, Y. If |X| =/= |Y|, then G (has a/has no) Hamiltonian cycle. If |X| = |Y|, then G (has a/has no) Hamiltonian chain connecting two vertices in X or Y. If |X| = |Y|+1, then G (has a/has no) Hamiltonian chain connecting one vertex in X and a vertex in Y
has no for all
a tree is
a connected graph that becomes disconnected upon the removal of any edge (each edge of a tree is a bridge)
A connected graph of order n is a tree if and only if
it has exactly n-1 edges and no cycle
Let G be a connected graph and a be an edge of G. Then a is a bridge if and only if
no cycle in G contains a
A graph G is a tree if and only if every pair of distinct vertices x and y are joined by
a unique chain
A spanning tree is
a tree containing all vertices of G
Every connected graph has a
spanning tree
Let T be a spanning tree of a connected graph G. Let a be an edge of G which is not an edge of T. Then there is an edge b of T such that
the graph T’ obtained from T by inserting a and deleting b is also a spanning tree of G
Let G = (V, E) be a graph. A proper coloring of G is
an assignment of a color to each vertex of G in such a way that adjacent vertices are assigned different colors
If a color is chosen from a set of k-colors, then the vertex-coloring is called
a k-coloring, whether or not all k colors are used
If G has a k-coloring, it is said to be
k-colorable
The smallest k, such that G is k-colorable, is called
the chromatic number of G X(G)
Let G be a graph of order n>=1. Then X(G) <= ?
n
X(G) = n if and only if
G = Kn
X(G) = 1 if and only if
G is a null graph Nn (a graph with no edges)
Let G be a graph and let H be a subgraph of G. Then X(G) ? X(H).
> =
If G has a subgraph equal to a complete graph Kp of order p, then X(G) ? p
> =
Let G be a graph of order n and let q be the largest order of an induced subgraph equal to Nq. Then X(G) >=
ceil (n/q)
A graph is called planar provided that
it can be represented by a drawing in the plane such that two edges-curves intersect only at vertex-points
Let G’ be a plan representation of G. Then any two edges can only intersect at ?
the vertices
Let G’ be a planar graph with n vertices, e edges, and r regions. Let the number of edges bordering the regions be, respectively, f1, f2, …, fr. Then Σfi from i to r =
= 2e = Σd(v) for each vertex in V
Euler’s formula: Let G be a connected planar graph with n vertices, e edges, and r regions. Then
r - e + n = 2
Let G be a connected planar graph. Then G has a vertex v such that deg(v) <= ?
5
Let G be a planar graph. Then |E| <= ?
3n-6
Let G be a bipartite planar graph. Then |E| <= ?
2n-4
Algorithm for a closed Eulerian trail starting with a1 = {x0, x1} ∈ E
- put i=1
- put W = {x0, x1}
- put F = {a1}
- while xi =/= x0 do (i) locate an edge a,i+1 = {xi, x,i+1} not in F (ii) put x,i+1 in W (x,i+1 may already be in W) (iii) put a,i+1 in F (iv) i++ and go back to 1
algorithm for spanning tree: let G be a connected graph of order n
(i) set F = E
(ii) while there is an edge F such that a is not a bridge of G = (V, F), set F = F - {a}
the terminal graph T = (V, F) is a spanning tree of G
BF-algorithm to grow a BSF-tree rooted at u (let u be any vertex)
- put i=1, U={u}, D(u) = 0, bf(u) = 1, F = Ø, and T = (U, F)
- if there is no edge in U that joins a vertex x in U to a vertex y in V-U, then stop. Otherwise, determine if there is an edge a = {x,y} with x in U and y in V-U such that x has the smallest breadth-first number bf(x) and do
(i) put bf(y) = i+1
(ii) put D(y) = D(x)+1
(iii) Set U = U ∪ {y} and F = F ∪ {a}
(iv) put T = (U, F)
(v) i++ and go back to 2
DF-algorithm to grow a DFS-tree rooted at u (let u be any vertex)
- put i=1, U = {u}, df(u) = 1, F = Ø, and T = (U, F)
- if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that x has the largest depth-first number df(x) and do
(i) put df(y) = i+1
(ii) set U = U ∪ {y} and F = F ∪ {a}
(iii) Put T = (U, F)
(iv) i++ and go back to 2
Algorithm for a distance-tree for u (Dijkstra’s algorithm): Let G = (V, E) be a graph of order n and let u be any vertex
- put i=1, U = {u}, D(u)=0, F=Ø, and T=(U,F)
- if there is no edge in G that joins a vertex x in U to a vertex y in V-U then stop. Otherwise, determine an edge a = {x, y} with x in U and y in V-U such that D(x) + c{x,y} is as small as possible and do
(i) set U = U ∪ {y} and F = F ∪ {a}
(ii) Put D(y) = D(x) + c{x,y} and go back to 2
Greedy algorithm for a minimum weight spanning tree (Kruskal’s algorithm): Let G=(V,E) be a weighted connected graph of order n with weight function c
- put F = Ø
- while there exists an edge a not in F such that F ∪ {a} does not contain the edges of a cycle of G, determine such an edge a with minimum weight and set F = F ∪ {a}
- put T = (U,F)
Prim’s algorithm for a minimum weight spanning tree: Let G=(V,E) be a graph of order n with weight function c and let u be any vertex
- put i=1, U1 = {u}, F1 = Ø, and T1 = (U1, F1)
- for i = 2, 3, …, n-1, do the following
(i) locate an edge ai = {x, y}of smallest weight such that x is in Ui and y is in V-Ui
(ii) Put U,i+1 = Ui ∪ {y}, F,i+1 = Fi ∪ {ai}, and T,i+1 = (U,i+1 , F,i+1)
(iii) increase i to i+1 - output T,n-1 = (U,n-1 , F,n-1) where U,n-1 = V
