Modelling with Graphs and networks

Question 1

what is a graph?

Answer 1

no axis, just a diagram made up of edges and vertices

Question 2

what are nodes/ vertices?

Answer 2

circles

Question 3

what are edges /arcs?

Answer 3

lines connecting the dots

Question 4

what is the degree/order of a vertex?

Answer 4

how many lines are coming out of that circle

Question 5

what is a connected graph?

Answer 5

it is possible to go from any vertex to any other vertex

Question 6

what is the relationship between the total order and the number of vertices?

Answer 6

• total order =12
• number of arcs = 6

total order will always be an even number

Question 7

what is a loop?

Answer 7

an edge that starts and finishes at the same vertex
Order of a loop =2

Question 8

what is a simple graph?

Answer 8

one with no loops and no multiple edges between two vertices

Question 9

what is a complete graph?

Answer 9

one where every vertex is connected to every other vertex by an edge

Question 10

How many arcs are in K(n)?

Answer 10

(n*n-1)/2

Question 11

what is a digraph?

Answer 11

a graph where at least one edge has direction associated with it

Question 12

what is a bipartite graph?

Answer 12

where the nodes are in two distinct sets. Each edge connects a emeber of the first set to a member in the second set. Points do not connect with any point within it’s own set

Question 13

what is an incidence matrix?

Answer 13

shows the arrangment of edges between each node

Question 14

what is isomorphism?

Answer 14

same number of nodes and orders of each node

between2 graphs

Question 15

what is a trail?

Answer 15

a sequence of joined up edges, such that no edge is repeated

nodes can be used more than once

Question 16

what is a path?

Answer 16

a sequenece of edges such that the end vertex on one edge is the dtart of the next. No vertex can be visited more than once

Question 17

what is a cycle?

Answer 17

a closed path- where the first and last node are the same

Question 18

what is a tree?

Answer 18

a simple connected graph with the minimum number of arcs. (If a single arc is removed it will no longer be a connected graph)

Question 19

what is a spanning tree?

of graph G

Answer 19

a graph which contains all the vertcies of graph G and is also a tree

Question 20

Q:

How many arcs are there in a tree with 10 nodes?

Answer 20

n-1
10-1=9

Question 21

A simple connected graph G, has 8 vertices.
* what is the minimum number of edges that G could have?
* what is the maximum number of edges that G could have?

Answer 21

• minimum: 7
• maximum: (complete graph)

Question 22

what is a eulerian/ traversible graph?

Answer 22

possible to make a trail that
* uses all edges once
* starts and ends at the same vertex

no nodes with odd degree

Question 23

what is a semi eulerian/ traversable graph?

Answer 23

possible to make a trail
* uses all edges once
* starts and ends at difference vertices

will have exactly two odd nodes- start and end point

Question 24

what is a network?

Answer 24

a value (weight) is added to each arc

Question 25

Answer 25

Question 26

Draw the incidence matrix for the following arrangement

Answer 26

Question 27

Answer 27