Graphs and networks - decision maths Flashcards
What is a walk?
A walk is a route through a graph along edges from one vertex to the next.
What is a path?
A path is a walk in which no vertex is visited more than once
What is a trail?
A trail is a walk in which no edge is visited more than once
What is a cycle?
A cycles is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
what is a hamilton cycle?
A cycle that includes every vertex
What are vertices (or nodes)?
The points on a graph
What are edges?
The lines between vertices
What is a subgraph?
A graph that doesn’t include all the edges or vertices.
What is the degree, valency or order of a vertext?
The number of edges attached to that vertex
What is the difference between a connected and non-connected graph?
Connected graph has all it’s vertices connected by edges. Non connected doesn’t.
What is a loop?
An edge that starts and finishes at the same vertex
What is a simple graph?
A graph with no loops and there is at most one edge connecting any pair of vertices.
What is a directed graph or digraph?
A graph where the edges have a direction associated with them (represented by arrows).
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A tree that includes all a graphs vertices
What is a complete graph?
A graph where every vertex is directly connected by a single edge to each of the other vertices.
What is an isomorphic graph?
A graph which show the same information as another graph but is drawn differently.
What is an adjacancy matrix?
A matrix that provides information about the connections between the vertices in a graph (each entry inb an adjacency matrix describes the number of arcs joining the corresponding vertices.
What is a distance matrix?
In a distance matrix, the entries represent the weight of each arc not the number of arcs.
What is Euler’s handshaking 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, including possibly zero.
What is a eulerian graph?
A graph with nodes with all even order
What is a semi eulerian graph?
A graph with only 2 odd nodes
