Graphs and networks Flashcards
a walk
a route through a graph along edges from one vertex to the next
Path
A walk in which no vertex is visited more than once
Cycle
A walk in which the end vertex is the same as the start vertically and no other vertex is visited more than once
Order/Degree/Valency
The number of edges incident to a vertex
Vertices
A singular point on a graph where edges can meet
Arcs
A link between two vertices (or the same one) that can be traversed
Simple Graph
There are no loops and at most one edge connecting any pair of vertices
Sub Graph
A graph where all the vertices and edges belong to the original graph
- A part of it essentially
Connected graph
a graph in which all of the vertices are connected by edges
Euler’s Handshaking Lemma (2 points)
- In any undirected graph, the sum of the degrees of the vertices is equal to 2 times the number of edges.
- The number of odd nodes must be even for this to be true
Loop
An edge that starts and finishes at the same vertex
Network/weighted graph
- graph with numbers associated with each edge (its weight)
Hamiltonian Cycle
A cycle that includes every vertex
Planar Graph
One that can be drawn in a plane such that no two edges meet except at a vertex (no crossing edges)
Spanning tree
A subgraph which includes all the vertices of the original graph and is also a tree
Adjacency Matrix
Each entry describes the number of arcs joining the corresponding vertex. (a vertex degree table)
Distance matrix
The entries represent the weight of each arc, not the number of arcs
