Graphs and Networks Flashcards Preview

A Level Further Maths Decision 1 > Graphs and Networks > Flashcards

Flashcards in Graphs and Networks Deck (26)
Loading flashcards...
1

What does a graph consist of

Points (vertices/nodes), the list of which may be referred to as the vertex set
Lines (edges/arcs), the list of which may be referred to as the edge set

2

Weighted graph or network

If a graph has a number (weight) associated with each edge

3

Subgraph of G

A graph, each of whose vertices belong to G and each of whose edges belong to G

A part of the original graph

4

The number of edges incident to a vertex

Degree/valency/order
A loop counts as 2
A vertex has either odd or even degree

5

Walk

A finite sequence of arcs such that the end vertex of one arc is the start vertex of the next

6

Path

A walk in which no vertex appears more than once

7

Trail

A walk in which no edge is visited more than once

8

Cycle/circuit

A closed path - finishes at the start vertex

9

Hamiltonian cycle

A cycle that visits every vertex exactly once

10

When is a graph connected?

If all its vertices are connected

11

Loop

An edge which starts and finishes at the same vertex

12

Simple graph

One with no loops and no more than one edge connecting any pair of vertices

13

Directed edges

Where the edges have a direction associated to them

Known as a digraph

14

Euler's handshaking lemma

In any undirected graph, the sum of the degrees of the vertices is equal to 2x the amount of edges. As a consequence, the number of odd vertices must be even, including possibly zero.

15

Tree

A connected graph with no cycles

16

Spanning tree of a graph

A subgraph which includes all the vertices of a graph and is also a tree

17

Complete graph

A graph in which every vertex is connected by a single edge to every other vertex
Symbolised by K
no. of nodes

18

Isomorphic graphs

Graphs which show the same information but may be drawn differently

19

Adjacency matrix

A table which shows the amount of connections between the vertices of a graph. Each entry describes the number of arcs joining the corresponding vertices

20

How many connections is a loop?

2

21

Distance matrix

The matrix associated with a weighted graph, the entries represent the weight of each arc, not the number, only write the weight if an edge connects them, no paths

22

Matrix for a directed graph

The values in the matrix represent the distance from the value on the left to the one on the top

23

Planar graph

One that can be drawn in a plane such that no two edges meet except at a vertex

24

When can you use the planarity algorithm?

When a graph contains a Hamiltonian cycle

25

Planarity algorithm setup

1. Find a Hamiltonian cycle
2. Draw a regular polygon with a neighbouring vertex for each connected vertices in the Hamiltonian cycle
3. Draw the edges that weren't in the Hamiltonian cycle inside the polygon
4. Draw the polygon again with no edges inside
5. Make a key to highlight the lines on the original polygon depending on whether they go on the inside or the outside.

26

Planarity algorithm execution

6. Draw one edge from the first polygon on the inside of the second
7. Note that line with an (i) next to it and then note any that cross that line with an (o) next to them and draw on the outside of the second polygon, ticking next to the note of the original line
8. Work down the list noting any that cross the next line as in the opposite region to them
9. Repeat until all lines have been drawn and ticked or it doesn't work at which stage it isn't planar