Decision Maths: 2. Graphs And Networks Flashcards

1
Q

What is a Graph

A

A graph consists of points (called vertices or nodes), which are connected by lines (edges or arcs)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a Weighted Graph/Network

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are Connected Graphs

A

Two vertices are connected if there is a path between them. A graph is connected if all its vertices are connected.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a Simple Graph

A

A simple graph is one which there are no loops and there is at most one edge connecting any pair of vertices.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a Directed Graph

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are Vertices/Nodes

A

The vertices/nodes are the points on a graph (A,B,C,D,E). This list is sometimes called the vertex set.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the Edges/Arcs

A

The edges/arcs are the lines connecting vertices (AB,AC,AF…). This list is sometimes called the edge set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Subgraph

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What the Degree or Valency of a Vertex (+How do we say if a Vertex is even or odd)

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

If you have odd degrees, will you have an even or odd amount of them

A

If you have odd degrees, you’ll always have an even number of them.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is A Walk

A

A walk is a route through a graph along edges from one vertex to the next.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is A Path

A

A path is a walk in which no vertex is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is A Trail

A

A trail is a walk in which no edge is visited more than once

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is A Cycle

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is A Hamiltonian Cycle

A

A Hamiltonian cycle is a cycle which includes every vertex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is A Loop

A

A loop is an edge which starts and finishes at the same vertex

17
Q

If a graph represented a telephone network, why would you want multiple edges going from one node to another?

A

So an organisation can make different calls at the same time.

18
Q

What is the Handshake Lemma

A

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.

19
Q

Can you draw a graph with an odd number of odd vertices?

A

No, it’s impossible

20
Q

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

A

n has to be odd

(To make an even number of odd vertices)

21
Q

What is A Tree

A

A tree is a connected graph with no cycles

22
Q

What is a Spanning Tree

A

A spanning tree is a subgraph, which includes all the vertices and is a tree

23
Q

What is A Complete Graph

A

A complete graph is a graph in which every vertex is directly connected by a single edge to each of the other vertices.

24
Q

a) How many edges are required to drawn Kn of a Complete Graph

b) How many edges are required to draw K10

A

a) n(n-1) / 2 = 1/2n (n-1)

b) (10 x 9) / 2 = 45

25
What is a Circuit
A walk in which the start vertex and the end vertex are the same
26
What are Isomorphic Graphs
Isomorphic graphs are graphs which show the same information but may be drawn differently.
27
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
28
What is an Adjacency Matrix
An adjacency matrix represents a graph or network (in a table for example)
29
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
30
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.
31
In a directed distance network, will the matrix be symmetrical or not?
In a directed distance network, the matrix will not be symmetrical.