Chapter 2- Graphs And Networks

Question 1

Graph

Answer 1

Consists of nodes connected by lines

Question 2

Weight

Answer 2

Number associated with each edge

Question 3

Sub graph

Answer 3

A graph who’s vertices belong to the original graph as do the nodes

Question 4

Valency

Answer 4

Number of edges incident on a vertex

Question 5

Walk

Answer 5

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

Question 6

Path

Answer 6

A walk in which no vertex is visited more than once

Question 7

Trail

Answer 7

A walk in which no edge is visited more than once

Question 8

Cycle

Answer 8

A walk in which the end vertex is the same as the start vertex and no vertex is visited more than once

Question 9

Hamiltonian cycle

Answer 9

A cycle that includes every vertex

Question 10

Connected graph

Answer 10

If all vertices are connected

Question 11

Loop

Answer 11

An edge that starts and finishes at the same vertex

Question 12

Simple graph

Answer 12

No loops and at most one edge connecting any pair of vertices

Question 13

Euler’s handshaking Lemma

Answer 13

Sum of degrees of vertices = 2 x the number of edges

Question 14

Tree

Answer 14

Connected graph with no cycles

Question 15

Spanning tree

Answer 15

A subgraph which includes all the vertices of the original graph and is also a tree

Question 16

Complete graph

Answer 16

A graph in which ever vertex is directly connected by a single edge to each other vertices

Question 17

Isomorphic graph

Answer 17

A graph which show the same information but may be drawn differently

Question 18

Planar graph

Answer 18

One that can be drawn in a place such that no two edges meet except at a vertex