Decision Maths: 2. Graphs And Networks Flashcards
What is a Graph
A graph consists of points (called vertices or nodes), which are connected by lines (edges or arcs)
What is a Weighted Graph/Network
If a graph has a number associated with each edge (usually called it’s weight), then the graph is known as a weighted graph or network.
What are Connected Graphs
Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.
What is a Simple Graph
A simple graph is one which there are no loops and there is at most one edge connecting any pair of vertices.
What is a Directed Graph
A directed graph is one in which the edges of the graph have a direction associated with them, the edges are known as directed edges. Directed graph is often abbreviated to digraph.
What are Vertices/Nodes
The vertices/nodes are the points on a graph (A,B,C,D,E). This list is sometimes called the vertex set.
What are the Edges/Arcs
The edges/arcs are the lines connecting vertices (AB,AC,AF…). This list is sometimes called the edge set
What is a Subgraph
A subgraph of G is a graph, each of whose vertices belong to G and each of whose edges belongs to G. It is simply a part of the original graph.
What the Degree or Valency of a Vertex (+How do we say if a Vertex is even or odd)
The degree, or valency, or order of a vertex is the number of edges incident (connected) to it.
(If a vertex has even degree we say it is even, similarly if the vertex has odd degree we say it is an odd vertex)
If you have odd degrees, will you have an even or odd amount of them
If you have odd degrees, you’ll always have an even number of them.
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 cycle 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 Hamiltonian Cycle
A Hamiltonian cycle is a cycle which includes every vertex
What is A Loop
A loop is an edge which starts and finishes at the same vertex
If a graph represented a telephone network, why would you want multiple edges going from one node to another?
So an organisation can make different calls at the same time.
What is 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. This result is known as the handshake lemma.
Can you draw a graph with an odd number of odd vertices?
No, it’s impossible
Example Question:
Graham is attempting to draw a graph which has vertices of the following orders.
2n-1, 2^n+2, n^2, 2n+1, 2^n-1
State a restriction on the value of n which would make the graph constructible
n has to be odd
(To make an even number of odd vertices)
What is A Tree
A tree is a connected graph with no cycles
What is a Spanning Tree
A spanning tree is a subgraph, which includes all the vertices and is a tree
What is A Complete Graph
A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices.
a) How many edges are required to drawn Kn of a Complete Graph
b) How many edges are required to draw K10
a) n(n-1) / 2 = 1/2n (n-1)
b) (10 x 9) / 2 = 45
What is a Circuit
A walk in which the start vertex and the end vertex are the same
What are Isomorphic Graphs
Isomorphic graphs are graphs which show the same information but may be drawn differently.
How can you tell if 2 graphs are Isomorphic (the same)
- Numbers of nodes
- Numbers of Arcs
- Order/Valency of the nodes
- Check both edge sets of the graph match up
What is an Adjacency Matrix
An adjacency matrix represents a graph or network
(in a table for example)
What does each entry in a non-weighted graph in an adjacency matrix describe?
In a non weighted graph each entry describes the number of arcs joining the corresponding vertices
What do the entries in a distance matrix in an adjacency matrix describe?
In a distance matrix the entries represent the weight of each arc, not the number of arcs.
In a directed distance network, will the matrix be symmetrical or not?
In a directed distance network, the matrix will not be symmetrical.
