Chapter 2 Graphs and Networks

Question 1

What is a graph?

Answer 1

A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs)

Question 2

What is a graph where each edge has a numbers associated with it called?

Answer 2

Weighted graph or a Network

Question 3

What is a weighted graph/network?

Answer 3

A graph withy numbers associated with each edge

Question 4

In a weighted graph, what are the numbers usually called?

Answer 4

Its weight

Question 5

What is a vertex?

Answer 5

A point in the graph

Question 6

What are vertices sometimes called?

Answer 6

Nodes

Question 7

What is an edge?

Answer 7

A line segment joining vertices

Question 8

What is the other word for edge?

Answer 8

Arc

Question 9

What do you need to be careful about with networks?

Answer 9

They aren’t usually drawn to scale
As a result the shortest path may not be the obvious path

Question 10

That is the list of vertices called?

Answer 10

Vertex set

Question 11

What is the list of edges called?

Answer 11

The edge set

Question 12

What is the vertex set?

Answer 12

The list of vertices

Question 13

What is the edge set?

Answer 13

The list of edges

Question 14

What is a subgraph?

Answer 14

A subgraph is part of the original graph

Question 15

When is a vertex and an edge incident?

Answer 15

If they are connected

Question 16

What is the degree of a vertex?

Answer 16

The number of edges incident to a particular vertex

Question 17

What are the other ways to say degree of a vertex?

Answer 17

Valency of a vertex
Order of a vertex

Question 18

What does even degree mean?

Answer 18

The vertex has an even number of incident edges
The degree of vertex will be an even number

Question 19

What deos odd degree mean?

Answer 19

The vertex has an odd number of incident edges
The degree of vertex will be an odd number

Question 20

What phrase can be used to say: The vertex has an even number of incident edges?

Answer 20

Even degree

Question 21

What phrase can be used to say: The vertex has an odd number of incident edges?

Answer 21

Odd degree

Question 22

What is a walk?

Answer 22

A walk is a route through a graph along edges from 1 vertex to the next

Question 23

What is a path?

Answer 23

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

Question 24

What is a trail?

Answer 24

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

Question 25

What is a cycle?

Answer 25

A cycle is a path in which the end vertex is the same as the start vertex

Question 26

What is a hamiltonian cycle?

Answer 26

A hamiltonian cycle is a cycle that includes every vertex

Question 27

What is the difference between a path and a trail?

Answer 27

A path doesn't visit any node more than once A trail doesn't visit any edge more than once

Question 28

What does it mean if 2 vertices are connected?

Answer 28

2 vertices are connected if there is a path between them

Question 29

What does it mean if a graph is connected?

Answer 29

A graph is connected if there is at least 1 path joining any 2 vertices in the graph

Question 30

What is a loop?

Answer 30

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

Question 31

What is a simple graph?

Answer 31

A simple graph is a graph in which there are no loops and there is at most 1 edge connecting any pair of vertices

Question 32

What is a directed graph? What is it often abbreviated to?

Answer 32

A graph in which the edges have a direction associated with them Digraph

Question 33

What do you know about degrees of vertices in a undirected graph?

Answer 33

The sum of the degrees of the vertices = 2 x the number of edges

Question 34

What do you know about the number of odd vertices? What is this result known as?

Answer 34

There must be an even amount of odd vertices This result is known as Euler's handshaking lemma

Question 35

What is a lemma?

Answer 35

A lemma is a mathematical fact used as a stepping stone to more important results

Question 36

What are the special graphs that you need to know?

Answer 36

A tree A spanning tree A complete graph Isomorphic graphs

Question 37

What is a tree?

Answer 37

A tree is a connected graph with no cycles

Question 38

What is a spanning tree?

Answer 38

A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree

Question 39

What is a complete graph?

Answer 39

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

Question 40

What is an isomorphic graph?

Answer 40

Isomorphic graphs are graphs which show the same information but may be drawn differently

Question 41

What is the special notation for complete graphs?

Answer 41

Question 42

What do you know must be true for isomorphic graphs?

Answer 42

They must have the same number of vertices of the same degrees These vertices must also be connected together in the same way

Question 43

What can you use to represent graphs and networks?

Answer 43

Adjacent matrices

Question 44

What does an adjacent matrix do?

Answer 44

Provided information about the connections between the vertices in a graph

Question 45

If you have a adjacent matrix which has all 0s in its leading diagonal what do you know is true?

Answer 45

There are no loops

Question 46

If you have a adjacent matrix which has a number greater than 1 what do you know is true?

Answer 46

Those 2 points share more than 1 arc between them

Question 47

What is a matrix associated with a weight graph called?

Answer 47

A distance matrix

Question 48

When do you use a distance matrix?

Answer 48

When you have a network

Question 49

What do you know about a distance matrix of a non directed network?

Answer 49

It will be symmetrical around the matrices leading diagonal

Question 50

What do you do in the distance matrix if there is no edge between 2 vertices?

Answer 50

You put a dash

Question 51

What is a planar graph?

Answer 51

A planar graph is a graph that can be drawn in a place such that no 2 edges meet except at a vertex

Question 52

Give an example of a planar graph?

Answer 52

Question 53

What fact does the planetary algorithm rely on?

Answer 53

That there is a hamiltonian cycle

Question 54

State the planetary algorithm

Answer 54

Question 55

What really helps when implementing the planetary algorithm?

Answer 55

Draw a regular polygon

Question 56

How does the planetary algorithm generally work?

Answer 56

Generally this works by: if edges crosses inside the hamiltonian cycle then they will both cross outside it. So the algorithm tries to separate all edges into a category that the cross or they don't. Therefore 1 of each pair can be directed outside the nodes

Question 57

What does a completed planetary algorithm question look like?

Answer 57

A completed answer should be the table of edges You only draw the isomorphic graph is asked

Question 58

What will stop the planetary algorithm?

Answer 58

There not being a hamiltonian cycle There being 2 outside edges crossing

Question 59

What happens if there ate 2 outside edges crossing? Why?

Answer 59

The graph isn't planar For there to be 2 outside edges crossing then if they are inside they will cross an inside edge by definition. So there is no possible solution

Question 60

What happens for the simplex algorithm if there isn't a hamiltonian cycle?

Answer 60

The algorithm is inconclusive