Graphs

Question 1

Definition of a graph

Answer 1

A graph consists of a finite set of points, called vertices (singular is vertex), and line segments or curves called edges, that start and end at vertices.
An edge that starts and ends at the same vertex is called a loop.

Question 2

Degree of vertex

Answer 2

Number of edges at that vertex.

Vertex with even number of edges is “even vertex”. And odd number of edges is”odd vertex.”

Question 3

Adjacent vertices

Answer 3

Two vertices connected by at least one edge.

Adjacent vertices = connected vertices

Question 4

Circuit

Answer 4

A path that begins and ends on same vertex.

Every circuit is a path. But Not every path is a circuit.

Question 5

Connected graph

Answer 5

If for any 2 of its vertices there is at least one path connecting them.

Question 6

Euler path

Answer 6

A path that travels though every edge of a graph once and only once. Each edge must be traveled and no edge must be retraced.

Question 7

Euler circuit

Answer 7

Travels though each edge of graph once and only once and must end on same vertex.

Question 8

Euler’s theorem

Answer 8

Following statements are true for connected graphs:
1-if a graph has exactly 2 odd vertices, then it has at least one Euler path, but no Euler circuit.
2-if a graph has no odd vertices, then it has at least one Euler circuit
3-if a graph has more than 2 odd vertices, then it has no Euler paths and no Euler circuits.

Question 9

Fleury’s algorithm

-what is the procedure?

Answer 9

1- If the graph has exactly two odd vertices, choose one of the two vertices as the starting point. If the graph has no odd vertices, choose any vertex as a starting point.
2- Number edges as you trace the graph according to the following rules:
-After you’ve traveled over an edge erase it. Show the erased edges as dashed lines.
-Open faced with a bridge of edges to trace choose an edge that is not a bridge travel over an edge that is a bridge only if there is no alternative.

Question 10

Purpose of Fleury’s algorithm

Answer 10

Finding A Euler’s path or a Euler’s circuit

Question 11

Is a Euler circuit and Euler path the same thing?

Answer 11

Every Euler circuit is a Euler path. However, NOT Every Euler path is a Euler circuit.

Question 12

Hamilton path

Answer 12

A path that passes through each vertex of a graph exactly once.

Question 13

Hamilton circuit

Answer 13

If a Hamilton path begins and ends at the same vertex and passes through all other vertices exactly once it is a Hamilton circuit.

Question 14

Difference between Hamilton path and Euler path

Answer 14

Hamilton path involves vertices.
Euler path involves edges.

Hamilton paths are used for ups drivers for specific locations.
Euler paths are used when every road needs to be used -for example garbage.

Question 15

Weighted graph

Answer 15

A graph whose edges have numbers attached to them. For example the cost of airfare from city A to city B.

Question 16

Traveling sales person problem

Answer 16

The problem of finding a Hamilton circuit in a complete weighted graph For which the sum of the weights of the edges is a minimum.

Question 17

Optimal Hamilton circuit

Answer 17

Also known as optimal solution. It is the minimum sum of weights of the edges in a weighted graph. (Traveling sales person problem)

Question 18

Brute force method

Answer 18

One method for finding an optimal Hamilton circuit. It uses the following steps:
1-model the problem with a complete weighted graph.
2- make a list of all the possible Hamilton circuits
3- Determine the sum of the weights of the edges for each of these circuits
4- The circuit with the minimum sum of weight is the optimal

Question 19

Nearest neighbor method of finding approximate Solutions to the traveling sales person problem

Answer 19

1-model the problem with the complete weighted graph.
2-Identify the vertex that serves as the starting point.
3- From the starting point, choose the edge with the smallest weight. Go to that vertex
4-Continue building the circuit, one vertex at a time, by moving along the edge with the smallest weight until all vertices are visited.