Graphs Flashcards
What is a graph?
A set of vertices connected by edges.
What is a walk?
A set of edges joined end-to-end.
What is a trail?
A walk where no edges are repeated but vertices can be repeated.
What is a cycle?
A trail that starts and ends at the same vertex.
No vertices can be repeated.
What is a connected graph?
A graph where it is possible to get from any vertex to any other vertex.
What is a simple graph?
A graph with no loops or multiple edges.
What is a simple-connected graph?
A simple graph that is connected.
What is a complete graph?
A simple graph with the maximum possible number of edges.
How many edges does the complete graph with n vertices have?
0.5(n(n-1))
What is a bipartite graph?
Simple graph.
Partitioned into two sets.
No edge connects two vertices in the same set.
What is a complete bipartite graph?
A bipartite graph.
Each vertex is joined to each other vertex in the other set by 1 edge.
How many edges does the complete bipartite graph with m vertices in the first set and n vertices in the second set have?
mn edges
What does an adjacency matrix show?
The number of edges that directly connect each pair of vertices.
What property does an adjacency matrix have about the lead diagonal?
It is symmetrical around the lead diagonal.
For a simple graph, the lead diagonal is all 0’s.
What is the complement of a graph?
The set of edges that could be added to the graph to make it complete.
What does the complement of a graph look like in terms of the graph’s adjacency matrix.
The complement switches all 0’s to ones and 1’s to 0’s, except the leading diagonal.
What is a tree?
A simple-connected graph with the minimum possible number of edges.
How many edges does a tree with n vertices have?
n-1 edges.
What is a traversable graph?
A graph that can be drawn as a trail (without going over the same edge twice).
What is an eulerian graph?
Eulerian graphs are traversable, with the trail starting and ending at the same vertex, so they are:
Connected
No vertices of odd degree
What is a semi-eulerian graph?
Traversable, with the trail starting and ending at different vertices, so they are:
Connected
2 vertices of odd degree.
What is a hamiltonian graph?
A graph that contains a cycle that passes through every vertex exactly once. (contains a hamiltonian cycle).
Not all the edges of the graph have to be used in the cycle.
What is a hamiltonian cycle?
A cycle that passes through every vertex in the graph exactly once.
What is a planar graph?
A graph that can be drawn with no edges crossing.
What is euler’s formula true for?
Any connected planar graph or convex polyhedron.
What is euler’s formula?
v-e+f=2
Where v is the number of vertices.
f is the number of faces
e is the number of edges
What is important to remember when counting f, the number of faces of a graph?
Includes the “outside” region.
What is kuratowski’s theorem?
A necessary and sufficient condition for a finite graph to be planar is that it does not contain a subgraph that is a subdivision of K5 or K3,3
What does it mean for two graphs to be isomorphic?
They have the same structure, but may be drawn in different ways.
