Define a graph in graph theory.

A graph consists of points, called vertices or nodes , which are connected by lines, called edges or arcs . A vertex may stand for an object, a place or a person, and an edge forms a connection between two vertices.

What is a loop, and what are multiple edges?

A loop is an edge that starts and ends at the same vertex. Multiple edges are two or more edges connecting the very same pair of vertices.

True or False? If two edges of a graph are drawn crossing each other, they are connected at the crossing point.

False. Edges are only ever connected at vertices . A graph is usually drawn so that edges do not overlap, but where they do the crossing point has no meaning at all.

Define a walk in a graph.

A walk is a finite sequence of edges in which the end vertex of one edge is the start vertex of the next. The total weight of a walk is the sum of the weights of the edges it uses.

In a graph, what is the difference between a path and a trail?

Both are walks, but a path repeats no vertex while a trail repeats no edge . So every path is also a trail, although not every trail is a path.

What is a cycle, and what is a tour?

A cycle is a closed path, so it finishes at the vertex it started from and repeats no other vertex. A tour is a walk that visits every vertex and returns to its start vertex.

What does it mean for a graph to be connected?

A graph is connected when all of its vertices are connected to one another. Two vertices count as connected if there is a path between them, so they need not be joined by a single edge.

What is a network, and what is a digraph?

A network is a graph whose edges each carry a number called the weight , often a distance, a time or a cost. A digraph is a graph whose edges have a direction, and those edges may only be travelled in the direction shown.

What is a tree, and what is a spanning tree?

A tree is a connected graph that contains no cycles. A spanning tree of a graph is a subgraph which is itself a tree and which includes all the vertices of the original graph.

When are two graphs isomorphic?

Two graphs are isomorphic when they have the same number of vertices and the degrees of corresponding vertices are the same . They carry the same information but may be drawn in completely different ways.

Define a planar graph .

A planar graph is one that can be drawn in a plane so that no two edges meet except at a vertex they are both connected to. A graph drawn with edges crossing may still be planar, provided it is possible to redraw it without any crossings.

What is a simple graph?

A simple graph is undirected and unweighted , and it contains no loops and no multiple edges . So every pair of vertices is joined by at most one edge, and no edge returns to the vertex it left.

Define the degree of a vertex.

The degree, or valency , of a vertex is the number of edges incident to it, meaning the number joined to it. A vertex is called odd or even according to whether its degree is odd or even.

What does Euler's handshaking lemma tell you about the number of odd vertices in a graph?

The number of odd vertices must always be even , and it may be zero. Because the degrees add to an even total, the odd ones have to pair up among themselves.

Define an Eulerian cycle .

An Eulerian cycle traverses every edge of a graph exactly once and returns to the vertex it started from. It is also known as an Eulerian circuit .

How does an Eulerian trail differ from an Eulerian cycle?

An Eulerian trail also uses every edge exactly once, but it starts and finishes at different vertices . An Eulerian cycle begins and ends at the same vertex.

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

A graph is Eulerian when every one of its vertices has even degree. It is semi-Eulerian when exactly two of its vertices have odd degree.

A graph has vertices of degree 2, 4, 3, 3 and 4. Where must an Eulerian trail through it start and finish?

An Eulerian trail must start at one of the two vertices of degree 3 and finish at the other. Those are the graph's only vertices of odd degree, and an Eulerian trail always runs between the two odd vertices.

True or False? An Eulerian cycle visits every vertex of a graph exactly once.

False. An Eulerian cycle covers every edge exactly once, not every vertex. Unlike an ordinary cycle it may pass through the same vertex more than once , and that is what makes covering every edge possible.

Why do Eulerian graphs matter in practical problems?

Eulerian graphs solve problems in which every edge has to be covered without any being repeated, such as inspecting every road in a network. The best known example is the route inspection, or Chinese postman, problem.

Define a Hamiltonian cycle .

A Hamiltonian cycle passes through every vertex of a graph once and only once, and returns to its start vertex. A graph that contains one is called a Hamiltonian graph .

What is a Hamiltonian path, and what makes a graph semi-Hamiltonian?

A Hamiltonian path visits every vertex of a graph exactly once but does not return to its start. A graph is semi-Hamiltonian when it contains a Hamiltonian path but no Hamiltonian cycle.

How do you show that a graph is Hamiltonian?

Write down an actual Hamiltonian cycle for it, such as ABCFDEA. There is no shortcut test, so exhibiting one is the only way, and a graph will often have several.

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

False. A Hamiltonian cycle must visit every vertex exactly once, and it will usually leave many edges unused. It is the vertices that have to be covered, not the edges.

What must a graph contain before the planarity algorithm can be applied to it?

The graph must contain a Hamiltonian cycle . The algorithm begins by redrawing that cycle as a polygon, so without one there is nothing to build on.

How does the planarity algorithm begin?

Draw a polygon with one vertex for each vertex of the graph, labelling them in the order of a Hamiltonian cycle . Then add every remaining edge of the graph inside the polygon, and write those edges down as a list.

In the planarity algorithm, what label is given to an edge that crosses an edge already labelled (I)?

The crossing edge is labelled (O) , for outside, because two edges that cross cannot both lie inside the polygon. (I) and (O) are opposite labels, so an edge crossing an (O) edge is labelled (I) in just the same way.

In the planarity algorithm, what tells you that a graph is planar, and what tells you it is not?

The graph is planar once every edge inside the polygon has been given a label. It is not planar if two edges that both cross the just-labelled edge also cross each other , since they would then need to share a label.

Once the planarity algorithm shows a graph is planar, how do you draw it without crossings?

Draw the polygon, then put every edge labelled (I) inside it and every edge labelled (O) outside it. Because no two edges sharing a label cross each other, the redrawn graph has no crossings at all.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms & Graph TheoryGraphs

Graphs (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/33

0Still learning

Know0

FrontGraph Theory
Define a graph in graph theory.

Was this flashcard helpful?

Cards in this collection (33)

Define a graph in graph theory.
A graph consists of points, called vertices or nodes, which are connected by lines, called edges or arcs.
A vertex may stand for an object, a place or a person, and an edge forms a connection between two vertices.
What is a loop, and what are multiple edges?
A loop is an edge that starts and ends at the same vertex.
Multiple edges are two or more edges connecting the very same pair of vertices.
True or False?
If two edges of a graph are drawn crossing each other, they are connected at the crossing point.
False.
Edges are only ever connected at vertices.
A graph is usually drawn so that edges do not overlap, but where they do the crossing point has no meaning at all.
Define a walk in a graph.
A walk is a finite sequence of edges in which the end vertex of one edge is the start vertex of the next.
The total weight of a walk is the sum of the weights of the edges it uses.
In a graph, what is the difference between a path and a trail?
Both are walks, but a path repeats no vertex while a trail repeats no edge.
So every path is also a trail, although not every trail is a path.
What is a cycle, and what is a tour?
A cycle is a closed path, so it finishes at the vertex it started from and repeats no other vertex.
A tour is a walk that visits every vertex and returns to its start vertex.
What does it mean for a graph to be connected?
A graph is connected when all of its vertices are connected to one another.
Two vertices count as connected if there is a path between them, so they need not be joined by a single edge.
Define a complete graph.
A complete graph is one in which every vertex is joined by an edge to every other vertex.
A complete graph with $n$ vertices is written $K_{n}$ .
True or False?
A complete graph with 4 vertices has 6 edges.
True.
Every vertex of $K_{4}$ is joined to each of the other 3, and each edge is shared between two vertices, giving $\frac{4 \times 3}{2} = 6$ edges.
The same reasoning gives $\frac{n (n - 1)}{2}$ edges for $K_{n}$ .
What is a network, and what is a digraph?
A network is a graph whose edges each carry a number called the weight, often a distance, a time or a cost.
A digraph is a graph whose edges have a direction, and those edges may only be travelled in the direction shown.
Define a subgraph.
A subgraph of a graph $G$ is a graph every one of whose vertices belongs to $G$ and every one of whose edges belongs to $G$ .
It is a graph built only from parts of $G$ .
What is a tree, and what is a spanning tree?
A tree is a connected graph that contains no cycles.
A spanning tree of a graph is a subgraph which is itself a tree and which includes all the vertices of the original graph.
When are two graphs isomorphic?
Two graphs are isomorphic when they have the same number of vertices and the degrees of corresponding vertices are the same.
They carry the same information but may be drawn in completely different ways.
Define a planar graph.
A planar graph is one that can be drawn in a plane so that no two edges meet except at a vertex they are both connected to.
A graph drawn with edges crossing may still be planar, provided it is possible to redraw it without any crossings.
What is a simple graph?
A simple graph is undirected and unweighted, and it contains no loops and no multiple edges.
So every pair of vertices is joined by at most one edge, and no edge returns to the vertex it left.
Define the degree of a vertex.
The degree, or valency, of a vertex is the number of edges incident to it, meaning the number joined to it.
A vertex is called odd or even according to whether its degree is odd or even.
Complete Euler's handshaking lemma, which holds for any undirected graph:
$sum of the degrees =______\times number of edges$
The completed result is:
$sum of the degrees = 2 \times number of edges$
Every edge adds 1 to the degree of each of the two vertices it joins, so it is counted twice in the total.
What does Euler's handshaking lemma tell you about the number of odd vertices in a graph?
The number of odd vertices must always be even, and it may be zero.
Because the degrees add to an even total, the odd ones have to pair up among themselves.
Define an Eulerian cycle.
An Eulerian cycle traverses every edge of a graph exactly once and returns to the vertex it started from.
It is also known as an Eulerian circuit.
How does an Eulerian trail differ from an Eulerian cycle?
An Eulerian trail also uses every edge exactly once, but it starts and finishes at different vertices.
An Eulerian cycle begins and ends at the same vertex.
What condition on the vertices makes a graph Eulerian, and what makes it semi-Eulerian?
A graph is Eulerian when every one of its vertices has even degree.
It is semi-Eulerian when exactly two of its vertices have odd degree.
A graph has vertices of degree 2, 4, 3, 3 and 4. Where must an Eulerian trail through it start and finish?
An Eulerian trail must start at one of the two vertices of degree 3 and finish at the other.
Those are the graph's only vertices of odd degree, and an Eulerian trail always runs between the two odd vertices.
True or False?
An Eulerian cycle visits every vertex of a graph exactly once.
False.
An Eulerian cycle covers every edge exactly once, not every vertex.
Unlike an ordinary cycle it may pass through the same vertex more than once, and that is what makes covering every edge possible.
Why do Eulerian graphs matter in practical problems?
Eulerian graphs solve problems in which every edge has to be covered without any being repeated, such as inspecting every road in a network.
The best known example is the route inspection, or Chinese postman, problem.
Define a Hamiltonian cycle.
A Hamiltonian cycle passes through every vertex of a graph once and only once, and returns to its start vertex.
A graph that contains one is called a Hamiltonian graph.
What is a Hamiltonian path, and what makes a graph semi-Hamiltonian?
A Hamiltonian path visits every vertex of a graph exactly once but does not return to its start.
A graph is semi-Hamiltonian when it contains a Hamiltonian path but no Hamiltonian cycle.
How do you show that a graph is Hamiltonian?
Write down an actual Hamiltonian cycle for it, such as ABCFDEA.
There is no shortcut test, so exhibiting one is the only way, and a graph will often have several.
True or False?
A Hamiltonian cycle must use every edge of the graph.
False.
A Hamiltonian cycle must visit every vertex exactly once, and it will usually leave many edges unused.
It is the vertices that have to be covered, not the edges.
What must a graph contain before the planarity algorithm can be applied to it?
The graph must contain a Hamiltonian cycle.
The algorithm begins by redrawing that cycle as a polygon, so without one there is nothing to build on.
How does the planarity algorithm begin?
Draw a polygon with one vertex for each vertex of the graph, labelling them in the order of a Hamiltonian cycle.
Then add every remaining edge of the graph inside the polygon, and write those edges down as a list.
In the planarity algorithm, what label is given to an edge that crosses an edge already labelled (I)?
The crossing edge is labelled (O), for outside, because two edges that cross cannot both lie inside the polygon.
(I) and (O) are opposite labels, so an edge crossing an (O) edge is labelled (I) in just the same way.
In the planarity algorithm, what tells you that a graph is planar, and what tells you it is not?
The graph is planar once every edge inside the polygon has been given a label.
It is not planar if two edges that both cross the just-labelled edge also cross each other, since they would then need to share a label.
Once the planarity algorithm shows a graph is planar, how do you draw it without crossings?
Draw the polygon, then put every edge labelled (I) inside it and every edge labelled (O) outside it.
Because no two edges sharing a label cross each other, the redrawn graph has no crossings at all.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:AlgorithmsNext:Minimum Spanning Trees