Final Flashcards
A vertex set π
A collection of points,vertices are dots,
An edge set πΈ
A collection of unordered pairs of vertices representing connections between them
edges are lines connecting these dots.
A walk from vertex
π£1To π£π
β
is a sequence of edges
{V1,V2}{V2,V3},β¦{Vn-1,Vn}
A circuit is a walk where the start and end vertices are the same:
A circuit is a walk where the start and end vertices are the same:
V1=Vn
A path
is a walk in which no vertex is revisited
Vi/=Vj for all i and j
Cycle:
A cycle is a special type of circuit with these properties:
It starts and ends at the same vertex (π£
1
=
π£
π
v
1
β
=v
n).
A walk vs A path
A walk may revisit vertices and edges, while a path cannot revisit vertices.
A circuit and a cycle
A circuit revisits the starting vertex and has a direction, while a cycle is undirected and only revisits the start/end vertex.
A path from x to y is a walk in G that has no repeated veritices
A path from x to y is a walk in G that has no repeated veritices
A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity
A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity
A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity
A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity
Euler Trail
Visit every edge exactly one, doesnβt necessarily start and end at the same vertex
The graph must be connected
Has exactly 2 vertices must have an odd degree
Euler circuit
Visit every edge once
Starts and ends at the same vertex
Graphs must be connected
Vertices have an even degree
