GRAPH THEORY

Question 1

A graph is

Answer 1

A set of lines, connecting points

Question 2

A loop is

Answer 2

An arc with the same node on either end

Question 3

Connected graph

Answer 3

Can slide from one node to any other

Question 4

Simple graph

Answer 4

No loops or multiple arcs

Question 5

Simply connected graph =

Answer 5

Both simple and connected

Question 6

Complete graph

Answer 6

Every possible pair of nodes fulfilled

Kn = 1/2n(n-1)
n = number of nodes

Question 7

A tree is a

Answer 7

Simply connected graph with minimum number of arcs - no cycles allowed

• has n-1 arcs

Question 8

Isomorphic graph

Answer 8

Graph bent and reshaped in a different form

Question 9

T/F - if the graph is complete then there are no zeroes in the incidence matrix

Answer 9

False - leading diagonal is all 0

Question 10

T/F - if the graph is simple than all the numbers in the incidence matrix all 0 or 1

Answer 10

True

Question 11

T/F - If all the numbers in the incidence matrix are 0 or 1, then the graph is simple

Answer 11

True

Question 12

T/F - the sum of numbers in the matrix is even

Answer 12

True - all the arcs counted twice

Question 13

Difference between undirected graph and digraph incidence matrices

Answer 13

Undirected symmetrical about its leading diagonal