# Chapter 12 - Graphs and Networks 1 Flashcards

## (*deep inhale*) Graphs and Networks, Traversals, Kruskal's and Prim's Algorithms, The route inspection and travelling salesman problems and Network Flows (*exhales*) this chapter is a huge tour...

Define a Graph, Vertex, Face and Edge.

- A Graph is a diagram involving a set of points and interconnecting lines.
- A Vertex is a point on a Graph.
- An Edge is a line joining two points.
- A Face is a region within the edges of a graph, including the singular region outside of it.

Define a complete graph?

A complete graph is a graph that has an edge connecting all possible pairs of vertices. The notation is Kₙ.

Define a complete bipartite graph?

A complete bipartite graph connects m vertices to n vertices. The notation is Kₙٖₘ

Define a degree in graph theory, and what is the relationship between the degrees and edges?

A degree in graph theory is defined as the number of connections each edge has. The total number of degrees is equal to 2 times the number of edges.

Define a Planar Graph.

A planar graph is a graph that can be embedded in the plane, in such a way that its edges only intersect at their endpoints. (no intersecting edges.)

What is Euler’s Formula for Planar Graphs?

Euler’s Formula, applicable for finite, connected, planar graphs:

v + f - e = 2.

Vertices + Faces - Edges (including infinite outside face) = 2

What are the two relationships connecting edges and graphs?

For a simple, connected, planar graph:

e ≤3v - 6 AND At least three edges, and every edge touches at most two faces.

2e ≥ 3f AND More than one edge.

State the triangle inequality.

The triangle inequality in Graph Theory:

AB + BC ≥ AC, where AC is the hypotenuse.

What is a walk traversal?

A walk traversal is a continuous journey across a graph with no restrictions on repeating edges or vertices.

What is a trail traversal? Therefore, what is a closed trail?

A trail traversal is a continuous journey across a graph that has no repeated edges. If it returns to the starting vertex, it is a closed trail.

What is a path traversal? Therefore, what is a cycle?

A path traversal is a continuous journey across a graph which has no repeated edges OR vertices. If you return to the start vertex, this is called a cycle.

What is a Hamiltonian Cycle?

A cycle which visits every vertex once and only once is called a Hamiltonian Cycle.

State the steps of Kruskal’s Algorithm.

Kruskal’s Algorithm:

Step 1: Choose the arc with minimum weight.

Step 2: Choose the arc with the least weight from the remaining arcs, avoiding those already chosen.

Step 3: If any nodes remain unconnected, go to Step 2.

State the steps of Prim’s Algorithm (on a graph).

Prim’s Algorithm:

Step 1: Choose any node to be the first the connected set.

Step 2: Choose the arc of minimum weight joining a connected node to an unconnected node. Add this arc to the spanning tree and the node to the connected set.

Step 3: If any unconnected nodes remain, go to Step 2.

State the steps of Prim’s Algorithm (on a graph).

Prim’s Algorithm (on a matrix):

Step 1: Select the first node.

Step 2: Cross out the row and number the column for the chosen node.

Step 3: Find the minimum undeleted weight in the numbered columns. Circle this value. The node for this row is the next chosen node.

Step 4: Repeat steps 2 and 3 until all nodes have been chosen.