Graphs Flashcards Preview

contemporary math > Graphs > Flashcards

Flashcards in Graphs Deck (19)
Loading flashcards...
1

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.

2

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.”

3

Adjacent vertices

Two vertices connected by at least one edge.
Adjacent vertices = connected vertices

4

Circuit

A path that begins and ends on same vertex.
Every circuit is a path. But Not every path is a circuit.

5

Connected graph

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

6

Euler path

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.

7

Euler circuit

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

8

Euler’s theorem

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.

9

Fleury’s algorithm
-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.

10

Purpose of Fleury’s algorithm

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

11

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.

12

Hamilton path

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

13

Hamilton circuit

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

14

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.

15

Weighted graph

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

16

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.

17

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)

18

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

19

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

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.