decision

Question 1

Kruskals algorithm

Answer 1

List arks in ascending order of weight

add arks in ascending order of weight not making cycles

Question 2

Prims algorithm

Answer 2

Choose any starting vertex

choose arc of least weight that joins to vertex already in the tree

Question 3

route inspection algorithm

Answer 3

Shortest distance through all nodes
identify all odd vertices ucing valency table
consider all pairings choose pair with smallest sums to repeat

Question 4

Eulerian graph or network

Answer 4

Is one which contains a trail that includes every edge and starts and finishes at the same vertex. This trail is called an Eulerian circuit.Any connected graph whos vertexes are all even is Eulerian

Question 5

Semi-Eulerian graph or network

Answer 5

one which contains a trail that includes every edge but starts and finishes and different vertices.Any connected graph with exactly two odd verteces is semi-Eurelian

Question 6

Weighted graph or network

Answer 6

If a graph as a number associated with each edge

Question 7

subgraph

Answer 7

is a graph, each of whose vertices belong to the original graph and each of whose edges belongs to the original graph. It is part of the original graph

Question 8

Degree,valency,order

Answer 8

The number of edges attached to a node

Question 9

A walk

Answer 9

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

Question 10

A Path

Answer 10

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

Question 11

A trail

Answer 11

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

Question 12

A cycle

Answer 12

Is a walk which the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 13

A Hamiltonian cycle

Answer 13

A cycle that includes every vertex

Question 14

connected graph

Answer 14

all the vertices are connected

Question 15

A loop

Answer 15

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

Question 16

simple graph

Answer 16

A graph with no loops and at most one edge connecting a pair of vertices

Question 17

directed graph (digraph)

Answer 17

if edges have a direction associated with them (directed edges)

Question 18

sum of orders in an undirected graph =

Answer 18

2 x the number of edges, number of odd notes must then be even (eulers handshaking lemma )

Question 19

tree

Answer 19

is a connected graph with no cycles

Question 20

spanning tree of a graph

Answer 20

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

Question 21

A complete graph

Answer 21

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

Question 22

isomorphic graph

Answer 22

Graphs which show the same information but are drawn differently