FM - Decision 1 - 2) Graphs and networks Flashcards
Definition of a graph
Consists of points (called vertices or nodes) which are connected by lines (called edges or arcs)
Definition of a subgraph
Graph where each of its vertices and edges belong to the original graph
Meaning and types of the degree (or valency or order) of a vertex
- Number of edges incident to it
- Even degree and odd degree
Definition of a walk
Route through a graph along its edges from one vertex to the next
Definition of a path
Walk in which no vertex is visted more than once
Definition of a trail
Walk in which no edge is visted more than once
Definition of a cycle
Walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once
Definition of a Hamiltonian cycle
Cycle which includes every vertex
Definition of a connected graph
Graph where all its vertices are connected
Definition of a loop
Edge that starts and finishes at the same vertex
Definition of a simple graph
Graph which has no loops and has at most one edge connecting any pair of vertices
Definition of a directed graph (or digraph)
Graph where its edges have directions associated with them
Meaning of Euler’s handshaking lemma
In any undirected graph, the sum of the degrees of the vertices is equal to double the number of edges. This means there must be an even number of odd nodes
Definition of a tree
Connected graph with no cycles
Definition of a spanning tree of a graph
Subgraph which includes all vertices of the original graph and is a tree
