7.1: Basic Graphs and Graphs Structure
- Page ID
- 181987
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
- Identify parts of a graph.
- Model relationships with graphs.
- Describe and identify walks, trails, paths, and circuits.
When you hear the word, graph, what comes to mind? You might think of the \(xy\)-coordinate system you learned about earlier in this course, or you might think of the line graphs and bar charts that are used to display data in news reports. The graphs we discuss in this chapter are probably very different from what you think of as a graph. They look like a bunch of dots connected by short-line segments. The dots represent a group of objects, and the line segments represent the connections, or relationships, between them. The objects might be bus stops, computers, Snapchat accounts, family members, or any other objects that have direct connections to each other. The connections can be physical or virtual, formal or casual, scientific or social. Regardless of the kind of connections, the purpose of the graph is to help us visualize the structure of the entire network to better understand the interactions of the objects within it.
Parts of a Graph
In a graph, the objects are represented with dots, and their connections are represented with lines like in Figure \(\PageIndex{2}\) displays a simple graph labeled G and a multigraph labeled H. The dots are called vertices; an individual dot is a vertex, which is one object of a set of objects, some of which may be connected. We often label vertices with letters. For example, Graph G has vertices a, b, c, and d, and Multigraph H has vertices e, f, g, and h. Each line segment or connection joining two vertices is referred to as an edge. H is considered a multigraph because it has a double edge between f and h and a double edge between h and g. Another reason H is called a multigraph is that it has a loop connecting vertex e to itself; a loop is an edge that joins a vertex to itself. Loops and double edges are not allowed in a simple graph.
To sum up, a simple graph is a collection of vertices and any edges that may connect them, such that every edge connects two vertices with no loops and no two vertices are joined by more than one edge. A multigraph is a graph in which loops or pairs of vertices are joined by more than one edge. In this chapter, most of our work will be with simple graphs, which we will call graphs for convenience.
Figure \(\PageIndex{2}\): A Graph and a Multigraph
It is not necessary for the edges in a graph to be straight. In fact, you can draw an edge any way you want. Graph theory focuses on which vertices are connected, not how the connections are drawn. In a graph, each edge can be named by the two letters of the associated vertices. The four edges in Graph X in Figure \(\PageIndex{3}\) are ab, ac, ad, and ae. The order of the letters is not essential when you name the edge of a graph. For example, ab refers to the same edge as ba.
A graph may have vertices that are not joined to other vertices by edges, such as vertex f in Graph X in Figure \(\PageIndex{3}\), but any edge must have a vertex at each end.
Name all the vertices and edges of graph F in Figure \(\PageIndex{4}.\) Does this graph have a loop?
- Answer
-
The vertices are v, w, x, y, and z. The edges are vw, vx, wx, wz, xy, and xz. The graph has no loop.
When listing the vertices and edges in a graph, work in alphabetical order to avoid accidentally listing the same item twice. When you are finished, count the number of vertices or edges you listed and compare that to the number of vertices or edges on the graph to ensure you didn’t miss any.
Name all the vertices and edges of Graph A.
Two vertices in a graph are called adjacent if they are connected directly by an edge. Two edges are called adjacent if they share a common vertex.
For example, in Figure \(\PageIndex{5}:\) Graph A, vertices s and t are adjacent, s and r are adjacent, s and q are adjacent, but vertices s and p are not, and also t and p are not adjacent.
Similarly, edges st and sr are adjacent, but sr and tq are not adjacent edges.
Name all the pairs of vertices of graph F in Figure \(\PageIndex{4}\) that are not adjacent.
- Answer
-
The vertices not adjacent in graph F are v and y, v and z, w and y, and y and z.
The “Google boys,” Sergey Brin and Laurence Page, transformed the World Wide Web in \(1998\) when they used the mathematics of graph theory to create an algorithm called Page Rank, which is known as the Google Search Engine today. The two computer scientists identified webpages as vertices and hyperlinks on those pages as edges because hyperlinks connect one website to the next. The number of edges influences the ranking of a website on the Google Search Engine because the websites with more links to “credible sources” are ranked higher. ("Page Rank: The Graph Theory-based Backbone of Google," September \(20, 2011,\) Cornell University, Networks Blog.
Analyzing Geographical Maps with Graphs
When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in Figure \(\PageIndex{7}.\) Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In Figure \(\PageIndex{7},\) the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex FYW has degree \(3.\) The degree of a vertex is the number of edges that connect to that vertex.
The degree of a vertex is the number of edges connected to it. The degree of a vertex can be either even or odd, depending on how many edges are connected to it. If a graph contains a loop, that loop contributes two to the degree of the vertex.
Think about the intersection of two roads, Daniel Parkway and Summerline, near FSW. That intersection is a vertex, and its degree is four.
Determine the degree of each vertex of Graph J in Figure \(\PageIndex{8}.\) If Graph J represents direct flights between a set of airports, do any of the airports have direct flights to two or more of the other cities on the graph? Also, determine if the degree is even or odd.
- Answer
-
For each vertex, count the number of edges that meet at that vertex. This value is the degree of the vertex. In Figure \(\PageIndex{9},\) the dashed edges indicate the edges that meet at the marked vertex.
Figure \(\PageIndex{9}\): Degrees of Vertices of Graph J with their even and odd characteristic.
The degree of \( a \) is \(3,\) indicating that \( a \) is ODD.
The degree of \( b \) is \(1,\) meaning that \( b \) is also ODD.
The degree of \( d \) is \(2,\) which classifies \( d \) as EVEN.
The degree of \( e \) is \(0,\) so \( e\) is also considered EVEN.
Finally, the degree of \( c\) is \(2,\) making \(c \) EVEN.
Representation of Graph as Boundaries.
Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the “Four Corners,” which is shown in the map in figure \(\PageIndex{10}.\)
In Figure \(\PageIndex{11},\) each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are not considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size, and distance toward the existence of the relationship of having a shared boundary.
A map of the Midwest is given in Figure \(\PageIndex{12}.\) Create a graph of the region in which each vertex represents a state and each edge represents a shared border.
- Answer
-
For each state, draw and label a vertex. Draw edges between any two states that share a common land border as figure \(\PageIndex{14}.\)
Figure \(\PageIndex{13}\): Edge Assigned to Each Pair of Midwestern States with Common Border Figure \(\PageIndex{14}\): Final Graph Representing Common Boundaries between Midwestern States
Could graphs be used to reduce Internet fraud? At least one researcher thinks so. Graph theory is used every day to analyze our behavior, particularly on social network sites. Alex Buetel, a computer scientist from Carnegie Mellon University in Pittsburgh, Pennsylvania, published a research paper in 2016 that discussed the possibilities of distinguishing the normal interactions from those that might be fraudulent using graph theory. Buetel wrote, “To more effectively model and detect abnormal behavior, we model how fraudsters work, catching previously undetected fraud on Facebook, Twitter, and Tencent Weibo and improving classification accuracy by up to \(68%\).” In the same paper, the researcher discusses how similar techniques can be used to model many other applications and even, “predict why you like a particular movie.” (Alex Beutel, "User Behavior Modeling with Large-Scale Graph Analysis," http://reports-archive.adm.cs.cmu.ed...-CS-16-105.pdf, May 2016, CMU-CS-16-105, Computer Science Department, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA)
Completeness and Subgraphs
Suppose that there were five strangers in a room, A, B, C, D, and E, and each one would be introduced to each of the others. How many introductions are necessary? One way to begin to answer this question is to draw a graph with each vertex representing an individual in the room and each edge representing an introduction as in Figure
Let's approach the problem by thinking about how many new people Person \(A\) would meet, then Person \(B,\) and so on, making sure not to repeat any introductions. The first graph in Figure shows Person \(A\) meeting Persons \(B, C, D,\) and \(E,\) for a total of \(4\) introductions. The next graph shows that Person \(B\) still has to meet Persons \(C, D,\) and \(E,\) for a total of \(3\) more introductions. The next graph shows that Person \(C\) still has to meet Persons \(D\) and \(E,\) which is \(2\) more introductions. The next graph shows that Person \(D\) only remains to meet Person \(E,\) which is one more introduction. The final graph has \(4+3+2+1=10\) edges representing \(10\) introductions.
A complete graph is one in which an edge connects every pair of distinct vertices.
The last graph in Figure is an example of a complete graph because an edge joins each pair of vertices. Another way of saying this is that the graph is complete because each vertex is adjacent to every other vertex. Figure complete graphs with three, four, five, and six vertices.
Subgraphs
Sometimes, a graph is a part of a larger graph. For example, the graph of South Florida Airports from Figure \(\PageIndex{7}\) is part of a larger graph that includes Orlando International Airport in Central Florida, which is shown in Figure A subgraph is a smaller graph section comprising a subset of the vertices and edges from the original graph. Every edge and vertex of the subgraph must come from the original graph.
The graph in Figure includes an additional vertex, MCO, and additional edges shown with dashed lines. The graph of direct flights between South Florida airports from Figure \(\PageIndex{7}\) is called a subgraph of the graph that also includes direct flights between Orlando and the same South Florida airports in Figure In general terms, if Graph B consists entirely of a set of edges and vertices from a larger Graph A, then B is called a subgraph of A.
Graph G and four diagrams are given in Figure \(\PageIndex{18}.\) Determine whether each diagram is or is not a subgraph of Graph G and explain why.
- Answer
-
Diagram J is not a subgraph of Graph G because edge ec is not in Graph G.
Diagram K is a subgraph of Graph G because all of its vertices and edges were part of Graph G.
Diagram L is not a graph at all because there is a line extending from vertex a that does not connect a to another vertex. So, Diagram L cannot be a subgraph.
Diagram M is not a subgraph of Graph G because it contains a vertex f, which is not part of G.
Recognizing Isomorphic (Equivalent) Graphs
Isomorphic graphs that represent the same pattern of connections can look very different despite having the same underlying structure. The edges can be stretched and twisted. The graph can be rotated or flipped. For example, in Figure each diagram represents the same pattern of connections. The isomorphic graph is also called an equivalent graph.
Two graphs are said to be isomorphic if they are structurally the same, even if they look different in a drawing.
Looking at Figure \(\PageIndex{19},\) how can we know that these graphs are isomorphic? We will start by checking for any obvious differences. Each of the graphs in Figure \(\PageIndex{19}\) has four vertices and five edges, so there are no differences. Next, we will focus on the degrees of the vertices, which have been labeled in Figure
As shown in Figure \(\PageIndex{20},\) each graph has two vertices of degree \(2\) and two vertices of degree \(3,\) so there are no differences.
When you name isomorphisms, one way to check that your answer is reasonable is to make sure that the degrees of corresponding vertices are equal.
Are the Graphs B1 and B2 in Figure \(\PageIndex{21}\) are isomorphic? Identify an isomorphism between them by listing corresponding pairs of vertices.
- Answer
-
Figure \(\PageIndex{22}\) shows how to transform Graph B1 to get Graph B2.
Vertex b corresponds to s, vertex c corresponds to r, vertex q corresponds to a, and vertex d corresponds to p.
Figure \(\PageIndex{22}\): Transform Graph B1 into Graph B2
A cycle is a path that starts and ends at the same vertex, with no repeated edges or vertices (except the starting and ending vertex, which must be the same). All cycle are circuit but not all circuit are cycle.
Consider graph figure \(\PageIndex{23}.\) The graph G contains quadrilateral cycle \((b, f, d, c),\) but graph S contains a triangle cycle \((m, r, o.)\) Also, graph S contains a triangle cycle, but graph G has no triangle. This means that the graphs are not isomorphic.
Walk, Path, Trails, Circuit, and Cycle
We know the basic parts of graphs, and we can distinguish one graph from another. It is time to really put our graphs to work for us. Many applications of graph theory involve navigating through a graph, very much like you would navigate through a maze. Imagine that you are at the entrance to a maze. Your goal is to get from one point to another as efficiently as possible. Maybe there are treasures hidden along the way that make straying from the shortest path worthwhile, or maybe you just need to get to the end fast. Either way, you definitely want to avoid any wrong turns that would cause unnecessary backtracking. Luckily, graph theory is here to help
- A walk is a sequence of vertices and edges where both edges and vertices can be repeated.
- A trail is an open walk where no edge is repeated, though vertices may be repeated.
- A path is a trail in which neither vertices nor edges are repeated.
A walk is the most basic way of navigating a graph, as it has no restrictions except for staying on it. We will call the walk by a different name when there are restrictions on which vertices or edges we can visit. For example, if we want to find a walk that avoids traveling the same edge twice, we will say we want to find a trail (or directed trail). If we want to find a walk that avoids visiting the same vertex twice, we will say we want to find a path (or directed path).
Walks, trails, and paths are all related.
- All paths are trails, but trails that visit the same vertex twice are not paths.
- All trails are walks, but walks in which an edge is visited twice would not be trails.
Since walks, trails, and paths are all related, closed walks, closed trails (circuits), and closed paths (directed cycles) are linked too.
- All circuits are closed walks, but closed walks that visit the same edge twice are not circuits.
- All directed cycles are circuits, but circuits in which a vertex is visited twice are not directed cycles.
We can visualize the relationship as in Figure and Figure
|
Term |
Description |
Edges Repeated? |
Vertices Repeated? |
|
Walk |
A sequence of edges and vertices |
Yes |
Yes |
|
Trail |
A walk with no repeated edges |
No |
Yes |
|
Path |
A trail with no repeated vertices |
No |
No |
|
Circuit |
A closed trail |
No |
Yes |
|
Cycle |
A closed path |
No |
No (except start/end) |
In many applications of graph theory, such as creating efficient delivery routes that begin and end at the same location, this requirement is often necessary. When a walk, path, or trail ends at the same location or vertex where it began, we call it a closed path. Otherwise, we call it open (it does not begin and end at the same location or vertex). The following table provides examples of closed walks, trails, and paths.
| DESCRIPTION | EXAMPLE | CHARACTERISTICS |
|---|---|---|
|
A closed walk is a walk that begins and ends at the same vertex. |
d → f → b → c → f → d |
Alternating sequence of vertices and edges Begins and ends at the same vertex |
|
A closed trail is a trail that begins and ends at the same vertex. It is commonly called a circuit. |
d → f → b → c → f → e → d |
No repeated edges Begins and ends at the same vertex |
|
A closed path is a path that begins and ends at the same vertex. It is also referred to as a directed cycle because it travels through a cyclic subgraph. |
d → f → b → c → d |
No repeated edges or vertices Begins and ends at the same vertex |
The same circuit can be named using any of its vertices as a starting point. For example, the circuit d → f → b → c → d can also be referred to in the following ways.
a → b → c → d → a is the same as
Let’s practice working with closed walks, circuits (closed trails), and directed cycles (closed paths). In the graph in Figure the vertices are major central and south Florida airports. The edges are direct flights between them
Suppose that you need to travel by air from Miami (MIA) to Orlando (MCO) and you are restricted to flights as represented on the graph. For the trip to Orlando, you decide to purchase tickets with a layover in Key West (EYW) as shown in Figure but you still have to decide on the return trip. Determine if your round-trip itinerary is a closed walk, a circuit,/or a directed cycle based on the return trip described in each part.
- You returned to Miami (MIA) by reversing your route.
- Your direct flight back left Orlando (MCO) but was diverted to Fort Lauderdale (FLL)! You flew to Tampa (TPA) from there before returning to Miami (MIA).
- Answer
-
- The whole trip was MIA → EYW → MCO → EYW → MIA. This is a closed walk because it begins and ends at the same vertex. It is not a circuit because it repeats edges. If it is not a circuit, then it cannot be a directed cycle.
- The whole trip was MIA → EYW → MCO → FLL → TPA → MIA. This is a closed walk because it begins and ends at the same vertex. It is a circuit because no edges were repeated. It is also a directed cycle because no vertices were repeated. So, it is all three!
Consider each sequence of vertices from Graph in Figure \(\PageIndex{28}.\) Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.
- b → c → d → e → f
- c → b → d → b → e
- c → f → e → d → b → c
- b → e → f → c → b → d
- Answer
-
\(1.\) First, check to see if the sequence of vertices is a walk by making sure that the vertices are consecutive. As you can see in Figure \(\PageIndex{27},\) there is no edge between vertex c and vertex d.
Figure \(\PageIndex{29}\) This means that the sequence is not a walk. If it is not a walk, then it can’t be a path, and it cannot be a trail, so it is none of these.
\(2.\) First, check to see if the sequence is a walk. As you can see in Figure \(\PageIndex{30},\) the vertices are consecutive.
Figure \(\PageIndex{30}\) This means that the sequence is a walk. Since the vertex b is visited twice, this walk is not a path. Since edge
bd \(3.\) First, check to see if the sequence is a walk. We can see in Figure \(\PageIndex{31}\) that the vertices are consecutive, which means it is a walk.
Figure \(\PageIndex{31}\) Next, check to see if any vertex is visited twice. Remember, we do not consider beginning and ending at the same vertex to be visiting a vertex twice. So, no vertex was visited twice. This means we have a walk that is also a path. The next check was to see if any edge was visited twice; none were. So, the sequence is a walk, a path, and a trail.
\(4.\) First, check to see if the sequence is a walk. We can see in Figure \(\PageIndex{32}\) that the vertices are consecutive, which means it is a walk.
Figure \(\PageIndex{32}\) Next, check if any vertex has been visited twice. Since vertex b is visited twice, this is not a path. Finally, check to see if any edges are traveled twice. Since no edges are traveled twice, this is a trail. So, the sequence of vertices is a walk and a trail.
Figure \(\PageIndex{32\) shows the floor plan of a house. Use the floor plan to answer each question.
- Draw a graph representing the floor plan in which each vertex represents a different room (or hallway), and edges represent doorways between rooms.
- Name a walk through the house that begins in the living room, ends in the garage, and visits each room (or hallway) at least once.
- Answer
-
\(1.\) We will need a vertex for each room, and it is convenient to label them according to the names of the rooms. Visualize the scenario in your head as shown in Figure \(\PageIndex{34}.\) You don’t have to write this step on your paper.
Figure \(\PageIndex{34}\): Assigning Vertices to Rooms Draw a graph to represent the scenario. Start with the vertices. Then, connect those vertices that share a doorway in the floor plan, as shown in Figure \(\PageIndex{35}.\)
Figure \(\PageIndex{35}\): Graph of the Floor plan Draw a walk that begins at vertex L, representing the living room, and ends at vertex G, representing the garage, making sure to visit every room at least once. There are many ways this can be done. You may want to number the edges to keep track of their order. One example is shown in Figure \(\PageIndex{36}.\)
Figure \(\PageIndex{36}\): Draw the walk from L to G \(2.\) Name the walk that you followed by listing the vertices in the order you visited them.
L → R → L → K → L → H → B → H → M → H → G
Connectedness
Before we can discuss finding the best delivery route, we must ensure that a route exists. For example, suppose that you were tasked with visiting every airport on the graph in Figure \(\PageIndex{37}\) by plane. Could you accomplish that task by only taking direct flight paths between airports listed on this graph? In other words, are all the airports connected by paths? Or are some of the airports disconnected from the others?
In Figure \(\PageIndex{37},\) we can see TPA is adjacent to PBI, FLL, MIA, and EYW. Also, there is a path between TPA and MCO through FLL. This indicates there is a path between each pair of vertices. So, it is possible to travel to each of these airports only by taking direct flight paths and visiting no other airports.
A graph is connected if there is a path joining every pair of vertices on the graph. If graphs are not connected, it is called disconnected.
Let’s take a closer look at graph X in Figure \(\PageIndex{38}.\) Focus on vertex a. There is a path between vertices a and b, but there is no path between vertex a and vertex c. So, Graph X is disconnected. The graph Y is connected because of vertex g.
When you are working with a planar graph, you can also determine if a graph is connected by untangling it. If you draw it so that none of the edges are overlapping, as we did with Graph X in Figure \(\PageIndex{39}\), it is easier to see that the graph is disconnected.
Versions \(2\) and \(3\) of Graph X in Figure each have the same number of vertices, number of edges, degrees of the vertices, and pairs of adjacent vertices as in version \(1.\) In other words, each version retains the same structure as the original graph. Since versions \(2\) and \(3\) of Graph X, do not have overlapping edges, it is easier to identify pairs of vertices that do not have paths between them, and it is more obvious that Graph X is disconnected. In fact, there are two completely separate, disconnected subgraphs, one with the vertices in {a, b, e}, and the other with the vertices {c, d, f}
Use Figure \(\PageIndex{41}\) to answer each question.
- Identify all the components of Graph E.
- Determine whether the graph is connected or disconnected, and explain your reasoning.
- Answer
-
- There is only one component in Graph E. It has the vertices {a, b, c, d}.
- The graph is connected because there is a path between vertex a and every other vertex. We can also see that Graph E is connected because it has only one component.
A bridge is an edge that, if removed, would disconnect the graph, meaning there would be at least two separate parts that are no longer connected.
Find the bridges in Graph G and Graph S
- Answer
-
In G, bridges are ab and de.
In S, bridges are nm, op, and pq.