Math 13 Ch4

A graph consits of a finite set of points, called vertices, and lines, called edges, that join pairs of vertices.

• To trace a graph means to begin at some vertex and draw the entire graph without lifting your pencil and without going over any edge more than once.
• Note: Euler graphs Cover all edges.

A graph is connected if it is possible to travel from any vertex to any other vertex of the graph by moving along successive edges. A bridge in a connective graph is an edge such that if it were removed the graph is no longer connected. Connected graphs are also called networks.

A vertex of a graph is odd if it is an endpoint of an odd number of edges of the graph. Similarly, a vertex is even if it is an endpoint of an even number of edges.

A graph can be traced if it is connected and has zero or two odd vertices.

• A path in a graph is a series is a consecutive edges in which no edge is repeated. The number of edges in a path is called its length. 
• NOTE:A designated start, end, and length.

• Start, end same vertex and cover all edges.
• NOTE: Must have even vertesies.

• If, while tracing a graph, we can travel completely through vertex A, then A must be an even vertex (note: traveling through includes if we start at a vertex A and then return later to vertex A)
• example: A and B are both even, A with 2, and B with 4.
•  
•  
• 

• If a graph can be traced, then it can have either zero or  two odd vertices.
• NOTE: With two odd vertices you must start at one of the odd vertices and you will end at the other vertice.
•  

A path in a graph is a series of consecutive edges in which no edge is repeated. The number of edges in a path is called its length.

A path containing all edges of a graph is called an Euler path. An Euler path that begines and ends at the same vertex is called a Euler Circut. A graph with all even vertices contains an Euler circut and is called an Eulerian graph.

• If a connected graph has all even vertices, we can find an Euler circut for it by beginning at any vertex and traveling over consecutive edges according to these rules.
• 1) After you have traveled over an edge, mark it. If all the edges for a particular vertex have been marked, then mark the vertex also.
• 2) Travel over an edge that is a bridge only if there is no alternative.  

• Find all the odd vertices, then map out how to connect them to make them all even with the smallest number of added pathways. (added the orange lines)
•  

• Draw a a graph and connect all the points as in the initial problem, then designate each vertex with a color, when designating colors you are not allowed to have the same color attached to one another.
•  

• When we assign numbers to the edges of a graph, the graph is called a weighted graph and the numbers of the edges are called weights. The weight of a path in a weighted graph is the sum of the weights of the edges of the path.
•  

A path passes through all the vertices of a graph exactly once is called a Hamilton path. If a Hamilton path begins and ends at the same vertex, then it is called a Hamilton circut. If a graph a Hamilton circut we will say it is Hamiltonian.

A complete graph is one in which every pair of vertices is jointed by an edge. A complete graph with n vertices is denoted by k_n.

• has (n-1)(n-2)(n-3)...3x2x1 Hamilton circuts. This number is written (n-1)! and is called (n-1) factorial.
• 

• There are algorithms that give good approximations to the Traveling Salesman without doing as much work. You will need to understand both how to find the solution to the traveling Sallesman Problem and how to approxamate using the Nearest Neighbor algorithm.
• Step 1: Start at any vertex x.
• Step 2: Of all the edges connected to x, choose any one that has the smallest weight. (There may be several with the smallest weight.) Select the vertex at the other end of this edge. This vertex is called the Nearest Neighbor algorithm.
• Step 3: Choose subsequent new verteces as you did when choosing the next vertex in the circut, choose one whose edge with the current vertex has the smallest weight.
• Step 4: After all vertices have been chosen, close the circut by returning to the starting vertex.

• Like the Nearest Neighbor, the Best Edge algorithm gives good approximations to the Traveling Salesman.
• Step 1: Begine by choosing any edge with the smallest weight.
• Step 2: Choose any remaining edge in the graph with the smallest weight.
• Step 3: Keep repeating Step 2; however, do not allow a circut to form until all verteces have been used. Also, because the final Hamilton circut cannot have three edges jointed to the same vertex, never allow this to happen during the construction of the circut.

• Compiling all possable trips in a weighted table and compairing all totals to find the lowest value. Most time consuming but a garentee.
• Step 1: List all Hamilton circuts in the graph.
• Step 2: Find the weight of each circut found in step 1.
• Step 3: The circuts with the smallest weights tells us the solution to the TSP.

• 2: What is the degree of the node (vertex)?
•   the number of connections it makes. 
• 3: What is the friendship paradox?
• Your friends have more friends then you do. 

When an edge has a direction it is called a directed edge. A graph in which all edges are directed is called a directed graph.

One-stage influence is the direct influence of one vertex on another vertex denoted by the direction of the edge. In Two-stage influence paths of length one and two are counted from one vertex to another vertex.

• (Project Evaluation and review Technique) summerizes the sequence relationships in the table using a special type of directed graph called PERT diagram. There are three important attributes:
• First, it represents each task by a vertex containing the number of months needed to complete each task.
• Second, the directed edges of the diagram show the sequence dependencies.
• Third, there are distinct start and end verteces which contain the tasks.
• 
•