Graph Theory - Terminology and Theory Flashcards
graph
A finite set of vertices and edges where each edge connects two vertices.
Example of an algebraic representation of a graph
G = (V, E)
V = {u, v, w}
E = {(u, v), (v, w), (u, w)}
True/False: In a graph, each edge must connect two vertices.
True
True/False: In a graph, there can be an edge connected to only one vertex.
False; In a graph, each edge must be connected to two vertices. (Also, an edge connected to one vertex leaves the other end of the edge disconnected).
T/F: Graphs must be composed of only one connected component/piece overall
False; there exists disconnected vertices, which consists of lone vertices - such graphs are composed of more than one piece/component
T/F: Graphs may be composed of more than one piece
True; Disconnected graphs are examples of graphs with more than one piece.
T/F: Edges may cross over each other
True
T/F: Edges cannot cross over each other
False; edges CAN cross over each other
T/F: Graphs can be drawn ONLY in one way
False
T/F: Graphs can be drawn in more than one/many ways
True
Adjacency
Two vertices u and v are adjacent to each other if and only if there exists an edge (u, v) touching u on one end and v on the other.
Incidence
“An edge (u, v) is incident to two vertices u and v” means there is an edge (u, v) that touches u on one end and v on the other end.
Self-loop
A curved edge that touches ONLY one vertex on both of its ends
Multi-graph
A graph that consists of self-loops and in some pairs of vertices, the vertices are adjacent to each other through multiple edges
Simple graph
A graph where there are NO self-loops and in every pair of vertices, the vertices are adjacent to each other through ONLY ONE edge.
Degree of a vertex
Number of edges incident on a vertex
Degree of a vertex only having a self-loop?
2
Degree of a lone/disconnected vertex?
0
Path
A contiguous sequence of vertices where in each pair of vertices, the vertices are connected to each other through ONLY one edge.
Simple path
A path in which all vertices are distinct; no repetition of any vertex
Length of path
No. of edges on a path; it is equal to no. of vertices - 1
subpath
A contiguous sub-sequence of vertices; Example: a subpath of a path from u to w consisting of vertices u, v, and w, is <u, v> and <v, w>
cycle/circuit
A path that begins and ends at the same vertex and all the edges are distinct
simple cycle
A cycle where except for the starting and ending vertex, all vertices are distinct/unique
acyclic
A graph with no simple cycles is acyclic
connected
A graph is connected if every vertex is reachable to and/or from all other vertices
reachable means?
A path exists
connected components
The set of vertices in a graph that are reachable to and from each other.
T/F: A lone vertex counts as a separate component.
True
Eulerian Cycle
A cycle/circuit which traverses EVERY edge of the graph EXACTLY ONCE.
Eulerian Path
A path which traverses EVERY edge of the graph EXACTLY ONCE.
What are some examples of problems/situations that would use a graph and require a Eulerian Path/Cycle?
Mail delivery, garbage collection, bioinformatics/DNA sequencing, circuit design, routing problems, communications networks, mapping genomes
Requirements for the existence of a Eulerian Cycle?
The graph is FULLY CONNECTED & the degrees of ALL vertices are EVEN.
Requirements for the existence of a Eulerian Path?
The graph is FULLY CONNECTED & the degrees of EXACTLY TWO vertices is ODD.
Euler’s 3rd Theorem
For a graph to exist, there must be an EVEN number of vertices with ODD degrees AND the total sum of degrees must equal to TWICE the total number of edges.
Purpose of Euler’s 3rd Theorem?
Proves the existence and possibility of a graph
Hamiltonian Cycle
A simple cycle that traverses EACH vertex of the graph ONLY ONCE.
Complete Graph
A graph in which every pair of vertices is adjacent.
Notation of a complete graph
K_n, where n is the total number of vertices in the graph.
Can a complete graph have an Eulerian Cycle? If yes, on what condition
Yes - given the total no. of vertices is ODD; in K_odd number, each vertex is connected to all other vertices, which makes up odd - 1, i.e. even
Can a complete graph have a Eulerian Path? If yes, on what conditon, if any?
K_2 is the only complete graph to have a Eulerian Path - for any n > 2, K_n does NOT have a Eulerian Path as either there are more than 2 odd-degree vertices (if n is EVEN) or there are NO odd-degree vertices (if n is ODD)
Bipartite graph
A graph where the vertices are partitioned into two sets and ALL the edges in the graph connect vertices from both sets BUT NOT WITHIN the sets.
