Define a graph in graph theory.

A graph consists of points, called vertices or nodes , which are connected by lines, called edges or arcs . It is a way of representing a set of objects together with the connections between them, such as places and the routes joining them.

In a graph, what does it mean for two vertices to be adjacent, and for two edges to be adjacent?

Two vertices are adjacent when an edge joins them directly. Two edges are adjacent when they share a common vertex.

What is a loop, and what are multiple edges?

A loop is an edge that starts and finishes at the same vertex. Multiple edges are two or more edges joining the same pair of vertices, and a graph is allowed to contain either.

True or False? If two edges of a graph are drawn crossing each other, the point where they cross is a vertex.

False. Edges are joined to one another only at vertices , so a crossing point with no vertex marked on it is just an artefact of the drawing. Graphs are usually drawn so that edges do not overlap, for exactly this reason.

Define the weight of an edge.

The weight of an edge is a number attached to it, most often a distance, a time or a cost. The weight of a walk is found by adding together the weights of all the edges it uses.

What is a cycle, and what is a tour?

A cycle , also called a circuit, is a path that starts and finishes at the same vertex, so it is a closed path. A tour is a walk that visits every vertex and then returns to its starting vertex.

Define a connected graph .

A connected graph is one in which every vertex is connected to every other vertex. Two vertices count as connected whenever there is a path between them, which does not require an edge joining them directly.

A network is a weighted graph , meaning a graph whose edges have each been given a numerical value. Networks are not usually drawn to scale, so the length of an edge on the page tells you nothing about its weight.

A digraph is a graph whose edges have been given a direction , making them directed edges. Each directed edge may only be travelled along in the direction its arrow indicates.

What four conditions make a graph a simple graph?

A simple graph contains no loops and no multiple edges . It is therefore the plainest kind of graph, with at most one edge between any pair of distinct vertices.

What is a subgraph, and what is a tree?

A subgraph of a graph is a graph whose vertices and edges all belong to the original graph. A tree is a connected graph that contains no cycles at all.

Define a spanning tree of a graph.

A spanning tree is a subgraph that is itself a tree and that includes every vertex of the original graph. Being a tree, it is connected and contains no cycles.

Define isomorphic graphs .

Isomorphic graphs are graphs that show the same information but are drawn in different ways. They have the same number of vertices, and the number of edges meeting each vertex matches up between them.

Define the degree (or valency) of a vertex.

The degree of a vertex is the number of edges incident to it, meaning the number of edges that meet it. A vertex is described as odd or even according to whether that number is odd or even.

By how much does a loop increase the degree of a vertex?

By two , rather than by one. A loop starts and finishes at the same vertex, so both of its ends are incident to that vertex and each end is counted separately.

What does the handshaking lemma tell you about the number of odd vertices?

The number of odd vertices in a graph is always even , and it may be zero. Since all the degrees add up to an even total, the odd degrees among them have to pair up.

What is the difference between an Eulerian cycle and an Eulerian trail?

Both use every edge of the graph exactly once . An Eulerian cycle returns to the vertex it set out from, while an Eulerian trail finishes at a different vertex from the one it began at.

True or False? An Eulerian cycle may pass through the same vertex more than once.

True. The condition is on the edges rather than the vertices: every edge is used exactly once, and nothing prevents the route arriving at a vertex again along a different edge. That is why an Eulerian cycle is not a cycle in the ordinary sense of the word.

What condition makes a graph Eulerian, and what makes it semi-Eulerian?

A graph is Eulerian when every one of its vertices has even degree, and it then contains an Eulerian cycle. It is semi-Eulerian when exactly two vertices have odd degree, and those two are where an Eulerian trail has to start and finish.

How can you tell quickly whether a graph is Eulerian or semi-Eulerian?

Ask whether the graph can be drawn without lifting your pen from the paper and without going over any edge twice. If it can, the graph is Eulerian or semi-Eulerian, because tracing it that way is exactly what using every edge once means.

Define a Hamiltonian cycle .

A Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once and returns to the vertex it started from. A graph that contains one is called a Hamiltonian graph .

How does a Hamiltonian path differ from a Hamiltonian cycle?

A Hamiltonian path visits every vertex exactly once but does not have to come back to where it began. A Hamiltonian cycle does the same and then returns to its starting vertex.

What makes a graph semi-Hamiltonian?

A graph is semi-Hamiltonian when it contains a Hamiltonian path but no Hamiltonian cycle . Every vertex can be visited once in a single journey, but there is no way of closing that journey back to its starting point.

True or False? A Hamiltonian cycle must use every edge of the graph.

False. A Hamiltonian cycle places its condition on the vertices : each one has to be visited exactly once. Any edges that are not needed in order to make that journey are simply left unused.

A graph has been shown to be Hamiltonian by writing down one Hamiltonian cycle. Could a different answer also be correct?

A graph can contain several different Hamiltonian cycles, so another student's answer may be just as correct. Any one of them is enough to establish that the graph is Hamiltonian.

International A Level (IAL)MathsEdexcelDecision 1FlashcardsAlgorithms & Graph TheoryGraphs

Graphs (Edexcel International A Level (IAL) Maths: Decision 1): Flashcards

Exam code: YMA01

1/30

0Still learning

Know0

FrontGraph Theory
Define a graph in graph theory.

Was this flashcard helpful?

Cards in this collection (30)

Define a graph in graph theory.
A graph consists of points, called vertices or nodes, which are connected by lines, called edges or arcs.
It is a way of representing a set of objects together with the connections between them, such as places and the routes joining them.
In a graph, what does it mean for two vertices to be adjacent, and for two edges to be adjacent?
Two vertices are adjacent when an edge joins them directly.
Two edges are adjacent when they share a common vertex.
What is a loop, and what are multiple edges?
A loop is an edge that starts and finishes at the same vertex.
Multiple edges are two or more edges joining the same pair of vertices, and a graph is allowed to contain either.
True or False?
If two edges of a graph are drawn crossing each other, the point where they cross is a vertex.
False.
Edges are joined to one another only at vertices, so a crossing point with no vertex marked on it is just an artefact of the drawing.
Graphs are usually drawn so that edges do not overlap, for exactly this reason.
Define the weight of an edge.
The weight of an edge is a number attached to it, most often a distance, a time or a cost.
The weight of a walk is found by adding together the weights of all the edges it uses.
Complete the three terms for moving through a graph:
A walk is a sequence of edges running from vertex to vertex. A $______$ is a walk in which no vertex is repeated, and a $______$ is a walk in which no edge is repeated.
The completed sentence is:
A walk is a sequence of edges running from vertex to vertex. A path is a walk in which no vertex is repeated, and a trail is a walk in which no edge is repeated.
Every path is therefore also a trail, but a trail need not be a path.
What is a cycle, and what is a tour?
A cycle, also called a circuit, is a path that starts and finishes at the same vertex, so it is a closed path.
A tour is a walk that visits every vertex and then returns to its starting vertex.
Define a connected graph.
A connected graph is one in which every vertex is connected to every other vertex.
Two vertices count as connected whenever there is a path between them, which does not require an edge joining them directly.
What is a complete graph, and how is one labelled?
A complete graph is a graph in which every vertex is joined by an edge to each of the other vertices.
A complete graph with $n$ vertices is written $K_{n}$ .
Define a network.
A network is a weighted graph, meaning a graph whose edges have each been given a numerical value.
Networks are not usually drawn to scale, so the length of an edge on the page tells you nothing about its weight.
Define a digraph.
A digraph is a graph whose edges have been given a direction, making them directed edges.
Each directed edge may only be travelled along in the direction its arrow indicates.
What four conditions make a graph a simple graph?
A simple graph contains no loops and no multiple edges.
It is therefore the plainest kind of graph, with at most one edge between any pair of distinct vertices.
What is a subgraph, and what is a tree?
A subgraph of a graph is a graph whose vertices and edges all belong to the original graph.
A tree is a connected graph that contains no cycles at all.
Define a spanning tree of a graph.
A spanning tree is a subgraph that is itself a tree and that includes every vertex of the original graph.
Being a tree, it is connected and contains no cycles.
Define isomorphic graphs.
Isomorphic graphs are graphs that show the same information but are drawn in different ways.
They have the same number of vertices, and the number of edges meeting each vertex matches up between them.
Define the degree (or valency) of a vertex.
The degree of a vertex is the number of edges incident to it, meaning the number of edges that meet it.
A vertex is described as odd or even according to whether that number is odd or even.
By how much does a loop increase the degree of a vertex?
By two, rather than by one.
A loop starts and finishes at the same vertex, so both of its ends are incident to that vertex and each end is counted separately.
Complete Euler's handshaking lemma, which holds for any undirected graph:
$sum of the degrees of the vertices =______\times the number of edges$
The completed lemma is:
$sum of the degrees of the vertices = 2 \times the number of edges$
Every edge has two ends, and each end adds one to the degree of the vertex it meets.
What does the handshaking lemma tell you about the number of odd vertices?
The number of odd vertices in a graph is always even, and it may be zero.
Since all the degrees add up to an even total, the odd degrees among them have to pair up.
What is the difference between an Eulerian cycle and an Eulerian trail?
Both use every edge of the graph exactly once.
An Eulerian cycle returns to the vertex it set out from, while an Eulerian trail finishes at a different vertex from the one it began at.
True or False?
An Eulerian cycle may pass through the same vertex more than once.
True.
The condition is on the edges rather than the vertices: every edge is used exactly once, and nothing prevents the route arriving at a vertex again along a different edge.
That is why an Eulerian cycle is not a cycle in the ordinary sense of the word.
What condition makes a graph Eulerian, and what makes it semi-Eulerian?
A graph is Eulerian when every one of its vertices has even degree, and it then contains an Eulerian cycle.
It is semi-Eulerian when exactly two vertices have odd degree, and those two are where an Eulerian trail has to start and finish.
How can you tell quickly whether a graph is Eulerian or semi-Eulerian?
Ask whether the graph can be drawn without lifting your pen from the paper and without going over any edge twice.
If it can, the graph is Eulerian or semi-Eulerian, because tracing it that way is exactly what using every edge once means.
A graph has vertices of degree $2$ , $4$ , $3$ , $3$ and $4$ . Is it Eulerian, semi-Eulerian, or neither?
It is semi-Eulerian, because exactly two of its vertices have odd degree, namely the two of degree $3$ .
An Eulerian trail therefore exists, and it must begin at one of those two vertices and end at the other.
Define a Hamiltonian cycle.
A Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once and returns to the vertex it started from.
A graph that contains one is called a Hamiltonian graph.
How does a Hamiltonian path differ from a Hamiltonian cycle?
A Hamiltonian path visits every vertex exactly once but does not have to come back to where it began.
A Hamiltonian cycle does the same and then returns to its starting vertex.
What makes a graph semi-Hamiltonian?
A graph is semi-Hamiltonian when it contains a Hamiltonian path but no Hamiltonian cycle.
Every vertex can be visited once in a single journey, but there is no way of closing that journey back to its starting point.
True or False?
A Hamiltonian cycle must use every edge of the graph.
False.
A Hamiltonian cycle places its condition on the vertices: each one has to be visited exactly once.
Any edges that are not needed in order to make that journey are simply left unused.
You are asked to show that a graph is Hamiltonian. What is the only way to do it?
Identify an actual Hamiltonian cycle and write it out, for example as the sequence of vertices $A B C F D E A$ .
There is no test on the degrees of the vertices that settles the question, so the cycle itself has to serve as the evidence.
A graph has been shown to be Hamiltonian by writing down one Hamiltonian cycle. Could a different answer also be correct?
A graph can contain several different Hamiltonian cycles, so another student's answer may be just as correct.
Any one of them is enough to establish that the graph is Hamiltonian.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:AlgorithmsNext:Minimum Spanning Trees