Graph Theory Flashcards
Graph Theory
Study of diagrams - networks, graphs
Vertices/nodes
Points on the graph
Edges/arcs
Lines that join vertices
Faces/regions
Area enclosed by edges
Loop
An edge that starts and ends at the same vertex
Multiple Edges
Two or more edges connecting the same two vertices`
Adjacent Vertices
Vertices that are connected by an edge
Weighted Graph/Networks
Graphs that have amounts/distances on each edge
Digraphs
Graphs that have directed edges/arcs
Undirected Graphs
Graphs with no directed edges
Simple Graph
An undirected graph with no loops and no multiple edges
Simple Weighted Graphs
An undirected graph with no loops and no multiple edges
Walk
A sequence of vertices for which each vertex in the sequence is joined to the next vertex by an edge - Can include repeat edges and vertices
Closed Walk
A walk that finishes at the same vertex
Open Walk
A walk that starts and finishes at different vertices
Path
A walk that involves no repeat use of edges and no repeat use of vertices
Open Path
A path that starts and finishes at different vertices
Closed Path - Cycle
A path that starts and finishes at the same vertex
Length
The number of edges the walk, path or cycle uses
Trail
A walk having no repeated edges (can revisit vertices)
Closed Trail
A trail that starts and finishes at the same vertex
Connected Vertices
When a path exists from one vertex to another
Adjacent Vertices
Two vertices connected by a path with only one edge
Connected Graph
When every vertex is connected to at least one other vertex
Bridge
Any edge in a connected graph which, when removed, leaves the graph disconnected
Complete Graph
A simple graph in which every vertex is connected to every other vertex by a single edge
Planar Graph
A graph that can be drawn in the plane, without its edges crossing over
Eulers Rule
F + V = E + 2
Subgraph
A selection of edges and vertices from a main graph
Tree
Any connected simple graph that contains no cycles
Bipartite
A graph in which the vertices can be divided into two disjoint sets such that each edge joins a vertex from one group to a vertex from the other group
Degree or Order of a Vertex
The number of edges meeting at that vertex
Odd Vertices
The order of a vertex is an odd number
Even Vertices
The order of a vertex is an even number
In-Degree
The number of edges coming into the vertex
Out-Degree
The number of edges coming out of the vertex
Traversable Networks
The network must be connected and have either zero or two odd vertices
Eulerian Trail
A trail in a connected graph that travels every edge only once - Repeated vertices permitted
Eulerian Circuit
A closed eulerian trail
Semi Eulerian Trail
An open eulerian trail
Hamiltonian Path
A path in a connected graph that visits every vertex in the graph only once
Hamiltonian Cycle
A closed hamiltonian path
Semi Hamiltonian
An open hamiltonian path
