Chapter 2 (Graphs) Flashcards
What’s a weight graph/ network
A graph with a number associated with each edge (usually called its weight).
Simple graph?
There are no loops and there are at most one edge connecting any pair of vertices (could be zero)
Subgraph?
A simple part of the original graph
What’s a degree or vertex
The number of edges incident to it
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
Trail
A walk in which no edge is visited more than once
Cycle
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
Hamiltonian cycle
A cycle which includes every vertex
Connected graphs
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected
A loop
Is an edge which starts and ends at the same vertex
The Handshake Lemma
In any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges, as a consequence, the number of odd vertices must be even
A tree
Is a connected graph with no cycles
Spanning tree
Is a subgraph, which includes all the vertices and is a tree
Complete graph
Is a graph in which every vertex is directly connected by a single edge to each of the other vertices
