Decision - Graphs and Networks

Question 1

What is a graph?

Answer 1

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

Question 2

What are points on a graph called?

Answer 2

Vertices or nodes

Question 3

What are lines on a graph called?

Answer 3

Edges or arcs

Question 4

What is a weighted graph?

Answer 4

A graph that has a number associated with each edge (usually known as its weight)

Question 5

What is a network?

Answer 5

A weighted graph

Question 6

How are 2 vertices connected?

Answer 6

If there is a path between them

Question 7

What is a connected graph?

Answer 7

A graph where all its vertices are connected

Question 8

What is a simple graph?

Answer 8

A graph in which there are no loops and there is at most 1 edge connecting any pair of vertices

Question 9

What is a directed graph?

Answer 9

A graph in which the edges of the graph have a direction associated with them, the edges are known as directed edges.

Question 10

What is directed graph abbreviated to?

Answer 10

Digraph

Question 11

What are all the vertices, or nodes, in a graph called?

Answer 11

The vertex set

Question 12

What are all the edges, or arcs, in a graph called?

Answer 12

The edge set

Question 13

What is a subgraph?

Answer 13

A subgraph of G is a graph, whos vertices belong to graph G and edges belong to G. It is simply a part of the original graph

Question 14

What is the degree of a vertex?

Answer 14

The number of edges incident to it

Question 15

What is the valency of a vertex?

Answer 15

The degree of a vertex

Question 16

What is an even vertex?

Answer 16

A vertex with an even degree/valency

Question 17

What is an odd vertex?

Answer 17

A vertex with an odd degree/valency

Question 18

What is a loop?

Answer 18

An edge where the start vertex and end vertex are the same

Question 19

What does a loop add to the valency?

Answer 19

2

Question 20

What is the rule with odd vertex’s?

Answer 20

If you have odd vertex’s, you will always have an even number of them

Question 21

What is a walk?

Answer 21

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

Question 22

What is a path?

Answer 22

A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next. No vertices can appear more than once

Question 23

What is a trail?

Answer 23

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

Question 24

What is a cycle?

Answer 24

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

Question 25

What is a Hamiltonian cycle?

Answer 25

A Hamiltonian cycle is a cycle which includes every vertex

Question 26

What is the handshake lemma?

Answer 26

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges, as a result, the number of odd vertices must be even

Question 27

Why must the number of odd vertices be even?

Answer 27

The handshake lemma

Question 28

What is the order of a graph?

Answer 28

the degree or valency

Question 29

What is a circuit?

Answer 29

A walk in which the start vertex and end vertex are the same

Question 30

What is a tree?

Answer 30

A connected graph with no cycles

Question 31

What is a spanning tree?

Answer 31

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

Question 32

What is a complete graph?

Answer 32

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

Question 33

What is the formula for the number of sides of the completed graph Kₙ?

Answer 33

0.5n(n-1)

Question 34

What is an algorithm?

Answer 34

A set of instructions which are followed to achieve a task

Question 35

What is the meaning of this shape in a flow chart?

Answer 35

Start/End

Question 36

What is the meaning of this shape in a flow chart?

Answer 36

A command to follow

Question 37

What is the meaning of this shape in a flow chart?

Answer 37

A decision/question

Question 38

What is a planar graph?

Answer 38

A planar graph is a graph which can be drawn in a plane such that no two edges meet except for at a vertex

Question 39

What is the planarity algorithm?

Answer 39

1. Identify a Hamiltonian cycle
2. Draw a polygon with vertices labelled to match the ones in the Hamiltonian cycle.
3. Draw edges inside the polygon to match the edges of the original graph not already represented
4. Make a list of all the edges “inside” the polygon
5. Choose any unlabelled edge in your list and label it “I” for inside. If all edges are now labelled then the graph is planar
6. Look at any unlabelled eges that cross the edge(s) just labelled:
   * If there are none then go back to step 5
   * If any of these edges cross each other then the graph is non-planar
   * If none of these edges cross each other, give them the opposite label the edge just labelled (“I” for inside or “O” for outside)
   * If all edges are now labelled, the graph is planar. Otherwise, go back to step 6.