Flashcards in Graphs Deck (19)
Definition of a graph
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.
Degree of vertex
Number of edges at that vertex.
Vertex with even number of edges is “even vertex”. And odd number of edges is”odd vertex.”
Two vertices connected by at least one edge.
Adjacent vertices = connected vertices
A path that begins and ends on same vertex.
Every circuit is a path. But Not every path is a circuit.
If for any 2 of its vertices there is at least one path connecting them.
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.
Travels though each edge of graph once and only once and must end on same vertex.
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.
-what is the procedure?
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.
Purpose of Fleury’s algorithm
Finding A Euler’s path or a Euler’s circuit
Is a Euler circuit and Euler path the same thing?
Every Euler circuit is a Euler path. However, NOT Every Euler path is a Euler circuit.
A path that passes through each vertex of a graph exactly once.
If a Hamilton path begins and ends at the same vertex and passes through all other vertices exactly once it is a Hamilton circuit.
Difference between Hamilton path and Euler path
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.
A graph whose edges have numbers attached to them. For example the cost of airfare from city A to city B.
Traveling sales person problem
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.
Optimal Hamilton circuit
Also known as optimal solution. It is the minimum sum of weights of the edges in a weighted graph. (Traveling sales person problem)
Brute force method
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