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