Graphs and Euler Circuits

• The module discusses the mathematics of graphs
• Intended learning outcome:
  • Define graph
  • Define Euler circuit
  • Determine Euler circuit in a graph
  • Solve the weights of the graph
  • Verify graph through Euler's formula

Graphs and Euler Circuits

• A graph is a set of points called vertices and line segments/curves called edges that connect vertices
• Graphs represent different scenarios
  • Vertices represent baseball teams
  • Edges represent if the two teams played against each other during the current season
• Vertices can be in any arrangement
• Important information is which vertices are connected by edges
• In a computer network, each vertex represents a computer
• Edges in a computer nework indicate which machines are directly connected to each other
• Vertices could represent a city
  • Edges could mean that there is a direct flight between the two cities

Constructing a Graph

• Example of students in a study group, with an “X” indicating they participate in the same study group
• A graph represents this information
  • Each vertex signifies a student
• An edge connects two vertices if the students study together

Questions after construction

• Which student is involved in most study groups with the others?
  • Amber is involved in the most study groups since she is connected to more edges than others
• Which student has only one study group in common with others?
  • Kayla has only one study group since she is connected by on edge only
• How many study groups does Laura have in common with others?
• Laura has two study groups since she is connected by two edges
• Vertex corresponding to Amber connects to more edges than the others
  • She is involved with more study groups (three) than the others
• Kayla is the only students with one study group in common
  • Her vertex is the the only one connected to just one edge
• Laura's vertex connects to two edge
• She shares two study groups with others

Terminologies used in Graph Theory

• In general, a graph can include vertices that are not joined to any edges

• All edges must begin and end at vertices

• Order - Number of its vertices

• Size - the number of its edges

• Parallel edges – two or more edges that join the same pair of distinct vertices

• Loop - An edge with the same endpoint

• Multigraph - A graph with no loops

• Pseudograph - A graph with at least one loop

• Simple graph – is a graph with no parallel edges and loops

• Multiple Edges – two or more edges connect the same vertices

• Loop - an edge that begins and ends at the same vertex

• Connected Graph – if any vertex can be reached from any other vertex by tracing along edges

  • Essentially, the graph consists of one "piece"

• Complete Graph (Kn) - a connected graph in which every possible edge is drawn between vertices (without any multiple edges)

  • Graph has n vertices in which there is exactly only one edge joining every pair of vertices

• Trivial graph (K₁) – a graph with one vertex and no edge

• Null graph - a graph with vertices and no edges

• A connected graph with every possible edge drawn between vertices without multiple edges is called a complete graph

• Whether edges are straight, curved, or their lengths doesn't matter

• The placement of the vertices is not important.

• What matters:

  • Which vertices are connected by edges

• Equivalent Graphs – two or more graphs in which the edges form the same connections of vertices in each graph

• The three graphs are considered equivalent graphs because the edges form the same connections of vertices in each graph

Euler Circuits

• Path - in a graph, a path can be thought of as a movement from one vertex to another by traversing edges
• If path ends at the same vertex at which it started, it is considered a closed path, or circuit
• Shown examples
  • one path would be A-B-A-C
  • the path A-D-F-G-E-B-A is a circuit because it begins and ends at the same vertex
  • the path A-D-F-G-E-H is not a circuit, as the path ends at a different vertex than the one it started at
• Euler's Circuit - a circuit that uses every edge, but never uses the same edge twice (the path may cross through vertices more than once)
• B-D-F-G-H-E-C-B-A-D-G-E-B is considered an Euler circuit
  • it begins and ends at the same vertex and uses each edge exactly once
• A-B-C-E-H-G-E-B-D-A is not an Euler circuit
  • Begins and ends at the same vertex but does not use edges DF, DG, or FG
• A-B-C-E-H-G-F-D-A-B- E-G-D-A begins and ends at A but uses edges AB and AD twice so it is not an Euler circuit
• Degree of a vertex - the number of edges that meet at a vertex

Eulerian Graph Theorem

• A connected graph is Eulerian if and only if every vertex of the graph is of even degree

Identifying graphs

• Ex. 1
  • a. has no Euler circuit
  • b. has an Euler circuit
• Ex. 2
  • has an Euler circuit
• By trial and error, one Euler circuit:
  • B – A -F-B-E- F-G-E-D-G-B-D-C- В
    • Method of location

Application of Euler Circuits

• A graph representation of subway maps show the tracks that trains traverse and junctions to switch trains
• Need possible journey that traverses the tracks and returns to starting point without traveling through a track more than once

Solution

• Find a trave route for the inspector that does not traverse the same track twice
• Determine if the graph is Eulerian and find an Euler circuit, if so
• Civic Center has a degree of 3
• Because a vertex has odd degree, graph cannot be Eulerian
• It is imposible for the inspector not ti travel at least one track twice

Euler Paths

• A connected graph contains an Euler path if and only if graph has two vertices of odd degree at most while all other vertices are of even degree
• Every Euler path must start at one of vertices of odd degree and end at the other

Application of Euler Path

• Photographer travles across road shown on a graph representaation of the following map
• Rents a car that need not be returned to the same city, so trip cen begin in any city
• Is it possible for the photographer to design a trip that traverses roads exactly once?

Solution

• A route that includes all of roads but doesn't cover any road twice corresponds to an Euler path of the graph
• Only two vertices are of odd degree (Alameda and Dover)
• Possibile for the photographer to plan a route to travel each road once
• Because A and D are vertices of odd degree, the photographer must start at one of these cities
• One Euler path:
  • A - B -C-D- - C - D-B-F-A-G-F-E-D
• Bicylist wants to mountain bike through trails of national park
• Graph representation of map is shown
• Bicyclist will be dropped off/picked up and doesn't have a preference for where she begins/ends
• Is it possible for acyclist to traverse all the trails wihtout repeating any portions of her trip?

Solution

• Consider the campground map as a graph.
• Route through all trails that does not repeat any trails corresponds to an Euler path
• Only two vertices (A and F) are of odd degree
• A/F Euler paths exist
• Futhermore, the path must begin at A/F and end at F/A
  • Trail with one Euler paths is A - B -C-D-E-B-G-F-E-C-A - F
• Figure depicts a floor plan of an art gallery
• Draw a gaht that represents the floor plan, whree vertices correspond to rooms and edges correspond to doorways
• Is it possible to tske stroll that passes through every doorway wihtout going through same doorway twice?
• If so, does it matter whether we return to starting point?

Solution

• Represent florr plsn wiht a graph
• Vertex represents each room
• Draw an edge between two vertices if doorway there
• Graph is equivalent to florr plan
• Tour gallery and pass thorugh every doorway once and we must find in ogur graph that used every edge once and no more
• Need to find an Euler path
• Two vertices are of odd degree and others are of even degree
• We know an Euler path exists but not an Euler circuit
  • Thereore, cannot pass through each doorway once and only once if we want to retrn to starting point by can do if end up eslewhere
• Furthermore, we know we start start vertex and we want to of odd degree (either romm C or room D
• One such path:
  • C – B -F-B-A-F-E-D-C - F - D No, it does not matter whether we return to starting point because an Euler path exists, not an Euler circuit

Weighted Graphs

• Hamiltonian Circuit
  • Path that ends and begins at the same vertex and passes through each vetex of gaht only once
  • Graph that contains a Hamitonian circuit is called Hamitonian e.g. A -B-C-D-E-F-G-A)
  • Graph that cointains Hamiltonian circuit is call Hamitonian
• If previous examole is cities, visit is priority

Dirac's Theroem

• Consider a graph with 3+ vertices/no multiple edges
• Let n be number of vertices in graph
• IF every vertex has degree of at least n/2 then graph must be HAmitonian
  • Important note:
    • If graph doesn't meet requirements of theorem, it still might be HAmitonian
• Apply Dirac Theroem
  • An edge is placed if there are direct flights between those vertices of a specific airline To see if the following graph is Hamilitonian
  • Also find a Haitian circuit and explain what if is in therms of flights

Solving

• There are six vertices, and every vertex had a degree of at least n/2 = 3
  • This graph then meets requirements of the theorem and it is Hamiltonian
• Find such a cicuit, in this case with the route Portland, Boise, Butte, SLCi, Reno, Sacramento, and finally back to Portland
• Apply Dirac's theorem to see if can draw a document to all offices and return one sending through same ofice twice which uses their delivery systems
• The graph is not connected so DRac's theromen does not apply, though route may still be found from trian and error, and one suche rouet in LA, to NY and Botston, Atlanta to Dalles adn Phoenix, San Francisto to LA
• A Weighted graph has an associated value called a weight with each edge, that can be used to calculate any desire quantity

Find Hamiltonian Circuits in a Weighted Graph

• A example:
  • Visitting six cities, what si total distances for three routes in total, using the distances flown between them that are listed
• If organize information in graph: - Begin by letting each city be represented by vertex, and draw lines between vertices - The total distance flown between them are shown on said lines

Solution

• Find three routes in total
• The distances associated are highlighted to find the toal amount
• Agloirthms in complete graph
• The step to get certain tasks in a route described by weighted graphs
• There can be possible no hshortcuts with weighed graphs
  • Thought these cns still be found through known greedy algorithsm

The Greedy Algorithsm

• The cheaper option will always prevail*

1. Choose start vertex and go along connected with simalleat weight,
2. After arrving at next, travle elogn with smallests vertex weight that are connected withnot, and continue doing so
3. Retrun to star ting

• It has to be start vertex A to find Hamiltonians circuit with weighsted graphs of figure shown
• Each node has weight, inthis case AD as the smallest path leading to DF as the smallerst weight is the DR value
• Each edge is with mallest weight
• Each value found wil hbe highlighted

The HAmitltionia circut has all values of vertex and return f

Final Answer Value: 42

The edge picking algorithsm

1. Mark the edge as smallest wight in a graph.
2. Mark edged as next smallest in graph and no compeltion
3. If a hamitotion is will alwasy have two vertex.
4. conitun these process but an mark anymore endes and finis h.

Final Result nameley BD with waith 2.

This the highlight edges will be the smallest

Algorithm has 3 stesteps, so it will be the one of highlight, and the name of each is added with there names to verify

Weighted graph application.

• Given the cost of flying between European city and the London city, London Berlin, and so on
• The greedy method is economic

Find a low cost out that only one site First draw the weighted graph with vertex represiting thecities will each labeled by flight labels

• Use an edge and travel long edges

Find Smallest Weight value London + parts and + Madrir

Final value

51935 dollars

Planarity and Euler's Foruma

• Three unity camp[anies need three pipes run threw houses, so it doessm cross att any point
• Can be expressed with terms unity A and B with hoses
• Can then be linked up with one way approach _Each of the HOuses
• Utilities compnaixes will repsent as vertex, so it draws an edge between two vertices and a pipe needs to run to the other
• Utilites graph is need solution that is planar

Plannar Graph

• Is a graph that can be drawn that dont notinterset with (vertices)
• In that graph that drawn as way and no edges.

The edges do not get to go on the floor

1. Find Non planar graph with 5 vertices denoted K_n is shown below,

2. If Araph as subgraph in not, plane is no as well,

3. As is a subgraph it contains Utilities that is not possible. Identify non planner group such as exapmplse and hghlighet them so can be easier

4. Shrinking a sub graph such is contracction.

Identify the Non planter graph Shrknik the bottom endes of graph, untilt disaspeer

The is where it has to be used as such , such the utiliest Grpah and k_5 serve bulding blocks. If fact anly non grpah willl alwasy have subgrop, which utlitis and has to be contratrced.

Non planner graph thorem

The graph is non planner and it contains utility and conratation. It gives an def test to graph in what ever is is not in the eduge Note: The grpah can be contracts t utility

• The graph of itself

Euler Formalu

• A Conneciton between various features of planner grouphs in addition is edges and vertices and look to faces in graph
• It divides into the differernt regiosn that are called faces,

Euler Formaul is alwasy true.