# Chapter 2 Graphs and Networks Flashcards

1
Q

What is a graph?

A

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

2
Q

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

A

Weighted graph or a Network

3
Q

What is a weighted graph/network?

A

A graph withy numbers associated with each edge

4
Q

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

A

Its weight

5
Q

What is a vertex?

A

A point in the graph

6
Q

What are vertices sometimes called?

A

Nodes

7
Q

What is an edge?

A

A line segment joining vertices

8
Q

What is the other word for edge?

A

Arc

9
Q

What do you need to be careful about with networks?

A

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

10
Q

That is the list of vertices called?

A

Vertex set

11
Q

What is the list of edges called?

A

The edge set

12
Q

What is the vertex set?

A

The list of vertices

13
Q

What is the edge set?

A

The list of edges

14
Q

What is a subgraph?

A

A subgraph is part of the original graph

15
Q

When is a vertex and an edge incident?

A

If they are connected

16
Q

What is the degree of a vertex?

A

The number of edges incident to a particular vertex

17
Q

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

A

Valency of a vertex
Order of a vertex

18
Q

What does even degree mean?

A

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

19
Q

What deos odd degree mean?

A

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

20
Q

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

A

Even degree

21
Q

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

A

Odd degree

22
Q

What is a walk?

A

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

23
Q

What is a path?

A

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

24
Q

What is a trail?

A

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

25
Q

What is a cycle?

A

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

26
Q

What is a hamiltonian cycle?

A

A hamiltonian cycle is a cycle that includes every vertex

27
Q

What is the difference between a path and a trail?

A

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

28
Q

What does it mean if 2 vertices are connected?

A

2 vertices are connected if there is a path between them

29
Q

What does it mean if a graph is connected?

A

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

30
Q

What is a loop?

A

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

31
Q

What is a simple graph?

A

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

32
Q

What is a directed graph?

What is it often abbreviated to?

A

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

Digraph

33
Q

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

A

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

34
Q

What do you know about the number of odd vertices?

What is this result known as?

A

There must be an even amount of odd vertices

This result is known as Euler’s handshaking lemma

35
Q

What is a lemma?

A

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

36
Q

What are the special graphs that you need to know?

A

A tree
A spanning tree
A complete graph
Isomorphic graphs

37
Q

What is a tree?

A

A tree is a connected graph with no cycles

38
Q

What is a spanning tree?

A

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

39
Q

What is a complete graph?

A

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

40
Q

What is an isomorphic graph?

A

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

41
Q

What is the special notation for complete graphs?

A
42
Q

What do you know must be true for isomorphic graphs?

A

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

43
Q

What can you use to represent graphs and networks?

A

44
Q

What does an adjacent matrix do?

A

Provided information about the connections between the vertices in a graph

45
Q

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

A

There are no loops

46
Q

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

A

Those 2 points share more than 1 arc between them

47
Q

What is a matrix associated with a weight graph called?

A

A distance matrix

48
Q

When do you use a distance matrix?

A

When you have a network

49
Q

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

A

It will be symmetrical around the matrices leading diagonal

50
Q

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

A

You put a dash

51
Q

What is a planar graph?

A

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

52
Q

Give an example of a planar graph?

A
53
Q

What fact does the planetary algorithm rely on?

A

That there is a hamiltonian cycle

54
Q

State the planetary algorithm

A
55
Q

What really helps when implementing the planetary algorithm?

A

Draw a regular polygon

56
Q

How does the planetary algorithm generally work?

A

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

57
Q

What does a completed planetary algorithm question look like?

A

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

58
Q

What will stop the planetary algorithm?

A

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

59
Q

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

A

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

60
Q

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

A

The algorithm is inconclusive