Flashcard decks

Graph theory midterm

67 flashcardsby Kayla
Study these flashcardsFree · spaced repetition · iPhone, Android, Mac & web

All cards

1
A vertex pair is said to be ___ to an edge if the vertices are the endpoints of the edge
incident
2
restate the Handshake lemma formula
sum of all degrees = 2 x the edges
3
restate the corollary of the handshake lemma
The number of vertices of odd degree is even
4
G and G' are ___ if there is a mapping between G and G' that maintains adjacency between all vertices.
isomorphic
5
A ___ graph is a graph in which any two vertices are adjacent.
complete
6
A __ is an alternating sequence of vertices and edges in a graph
walk
7
The length of a walk is equal to the number of __ along it
edges
8
If all of the vertices of a walk are distinct, then it is a ___
path
9
If all of the edges of a walk are distinct, then it is a
trail
10
If a trail's first and last vertex are the same, it is called ___
closed
11
Another word for a closed trail is a ___
circuit
12
If a walks first and last vertices are the same, then it contains a ___
cycle
13
A graph is __ if there is a path from any vertex to any other vertex
connected
14
A maximally connected subgraph is called a __
component
15
a __ vertex is a vertex that, upon removal, increases the number of components
cut
16
An edge is a ___ if and only iff x,y is not in a cycle
bridge
17
A __ is a connected, acyclic graph
tree
18
A ___ is a graph in which every component is a tree
forest
19
A __ subgraph is a subgraph that contains all of the vertices of the original graph
spanning
20
A spanning subgraph is a spanning __ if it is connected and acylic
tree
21
Every connected graph is a __ __
spanning tree
22
a tree with n vertices has ___ edges
n-1
23
a forest with n vertices and k components has ___ edges
n-k
24
A tree having atleast 2 vertices has atleast 2 vertices of degree _
1
25
The greedy algorithm is also called ___ algorithm
Kruskals
26
true or false, step two of the greedy algorithm has you choose edges from all adjacent edges to vertices already chosen.
false
27
the greedy algorithm finds an __ spanning tree
economical
28
Other than the greedy algorithm, what is another way to find an economical spanning tree?
prims algorithm
29
what problem is this? An explorer wishes to explore all the routes between a number of cities. can a tour be found that traverses each route only once?
explorers
30
what problem is this? A traveler wishes to visit a number of cities. Can a tour be found which visits each city exactly once?
travelers
31
___ circuit is a circuit that contains all edges of G
Eulers
32
eulers __ is a trail that contains all edges in G
trail
33
What is the name of a famous problem in which citizens wanted to travel to every bridge in their city once and end up back at home?
Konigsberg bridge problem
34
If you want to tell if you can draw a figure without lifting the pencil, you'll look for a Euler __
trail
35
If G has atleast 2 vertices and each vertex has even degree then G contains a
Euler circuit
36
If G has atleast 2 vertices and exactly two vertices have odd degree then G contains a
Euler trail
37
What algorithm can be used to find Euler circuits?
Fleurys algorithm
38
A subgraph contstructed by only specific vertices in G is ___ by the vertex set it is constructed by. Denoted G[V']
induced
39
True or false, any two spanning trees have an edge in common
false
40
the traveling salesman problem boils down to finding a __ __ of least cost in G
Hamiltonian cycle
41
A cycle containing all of the vertices of a graph is called a ___ cycle
Hamilton
42
If some graph has a hamilton cycle, then removing n vertices means there will be atlmost n __
components
43
restate diracs theorem (in your own words, mark correct if close enough)
if G has atleast 3 vertices, and the lowest degree of G is atleast 1/2 of the vertices in G, then G has a hamilton cycle
44
true or false, the greedy algorithm can be used to get a lower bound on the traveling salesman problem
true
45
A __ graph is a graph where the edges only intersect at the vertices
plane
46
A graph is __ if it is isomorphic to a plane graph
planar
47
Each plane graph has an unbounded face called the ___ face
infinite
48
restate Euler's polyhedron formula
If a connected plane graph has n vertices, m edges, and f faces, then n - m + f = 2
49
the __ of a graph is the number of edges in the shortest cycle of the graph
girth
50
a planar graph has |E(G)| at most ___ if G is acyclic
n - 1
51
a planar graph has |E(G)| at most ___ if G is cyclic
girth / girth - 2 ( n - 2)
52
restate the steps to proving diracs theorem (youll have to judge its correctness)
maximally non hamiltonian path, endpoints u and v cannot both be adjacent to vi and vi+1 so they are bounded by <= n -1. contradiction to them being >= n
53
restate the steps to proving eulers polyhedron theorem (youll have to judge its correctness)
a tree follows the formula, assume a non tree follows the formula, show that removing an edge from a cycle keeps the formula unchanged.
54
prove that if every vertex has degree >= k, there is a path of atleast k
the max length path must have k neighbors in it because the endpoint will be adjacent to atleast k neighbors and if those neighbors arent in the path then it isnt the longest path
55
prove that in a group of two or more people, two will have the same number of friends
assume that all degrees are distinct, 0 and n-1 cannot coexist.
56
prove that if each vertex has even degree then there are no bridges
assume there is a bridge, if you remove it then there will be exactly 1 odd degree in each component which is impossible due to the handshake lemma
57
if a graph has n >=3 and d(v) + d(u) >=n then it is hamiltonian
same as diracs theorem proof
58
prove that if a graph has an xy trail then it has an xy path
shortest trail can be collapsed to have no repeated vertices, so there is also a path
59
prove that every graph has an even number of odd degree vertices
split the handshake lemma into evens and odds, simplify to odds = evens
60
prove that an edge is a bridge iff it is not in a cycle
bridges have no alterative path to them, so theres no cycle (which is two paths between vertices)
61
prove that a graph is a forest iff every pair of vertices has only one path between them
longest path endpoints must be degree 1
62
prove that a connected graph with at least on eedge has a euler circuit iff every vertex has even degree
incident edges are pairs of enterance and exit edges
63
If g is a tree then it is __ connected and __ acyclic
minimally maximally
64
describe kruskalsreedy algorithm in one sentence
Pick the lowest cost edge from anywhere without making a cycle
65
describe prims algorithm in one sentence
Start at a vertex and pick cheap edges incident to already chosen edges
66
describe the reverse delete algorithm (reverse greedy) in one sentence
Remove the most expensive edge without disconnecting the graph
67
describe fleurys algorithm in one sentence
Choose unused edges, avoiding bridges, until every edge is used once
Study all 67 cards for free