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