Flashcards in Decision Maths Chapter 2 Definitions Deck (20)

Loading flashcards...

1

## Graph

### A group of points (called vertices or nodes) that are connected by lines (Edges or Arcs).

2

## Weighted Graph

### A graph that has a number associated with each edge.

3

## Subgraph

### A graph each of whose vertices belongs to G and each of whose edges belongs to G. It is simply a part of the original graph.

4

## Degree/Valency/Order of a vertex

### The number of edges incident to it.

5

## Walk

### A route through a graph along edges from one vertex to the next.

6

## Path

### A walk, in which no vertex is visited more than once.

7

## Trail

### A walk in which no edges are visited more than once.

8

## Cycle

### A walk, in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

9

## Hamiltonian Cycle

### A cycle that includes every vertex.

10

## Connected Graph

### A graph where all vertices are connected.

11

## Loop

### An edge that starts and finishes at the same vertex.

12

## Simple Graph

### A graph in which there are no loops and there is at most one edge connecting any pair of vertices.

13

## Directed Graph

### If the edges of a graph have an associated direction.

14

## Euler's Handshake Lemma

### The sum of the degrees of the vertices is equal to 2 x the number of edges.

15

## Tree

### A graph with no cycles

16

## Spanning Tree

### A subgraph that involves all of the vertices and is also the tree.

17

## Complete Graph

### A graph in which every vertex is directly connected by a single edge to each of the other vertices.

18

## Isomorphic Graph

### Graphs that show the same information but may be drawn differently.

19

## Adjacency Matrix

### A matrix where each entry describes the number of arcs joining the corresponding vertices.

20