Modelling With Graphs

Question 1

Nodes/Vertices

Answer 1

Points on a graph, usually connected by arcs or edges

Question 2

Arcs/Edges

Answer 2

Lines that connect nodes

Question 3

What is a Network

Answer 3

A weighted graph - where the edges of a graph have a corresponding value (weights)

Question 4

What is a simple graph

Answer 4

A graph in which there are no loops and each pair of vertices is connected by at MOST one arc (can be not connected)

Question 5

Directed graph

Answer 5

A graph in which at least one of the arcs has a direction associated with it

Question 6

Degree/Order/Valency

Answer 6

The number of arcs incident to a vertex

Question 7

Walk

Answer 7

Route through a graph along edges from one node to the next

Question 8

Path

Answer 8

A walk where no node is visited more than once

Question 9

Trail

Answer 9

Walk where no edge is visited more than once

Question 10

Cycle

Answer 10

Walk where start and end vertex are the same, no other node is visited more than once

Question 11

Hamiltonian cycle

Answer 11

Cycle where every node is visited

Question 12

Connected Graph

Answer 12

A graph where every vertex is connected by a walk

Question 13

The handshake lemma

Answer 13

In an undirected graph:

Sum of valences = 2(#edges)
Therefore the number of odd vertices must be even

Question 14

Tree

Answer 14

Connected graph with no cycles

Question 15

Spanning Tree

Answer 15

Sub Graph which includes every node and is also a tree

Question 16

A complete Graph

Answer 16

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

Question 17

Edges to draw Kn

Answer 17

n^2 - n
—————
2

Question 18

Isomorphic graph

Answer 18

Two graphs are isomorphic if they show the same information but are constructed different

Question 19

What does a graph need to be isomorphic

Answer 19

• Same number of vertices
• same set of orders
• Each vertex must have the same set of Valencies of connected nodes as the corresponding vertex in the other graph (see book)