Flashcards in Graphs and Networks Terminology Deck (17):

1

## Subgraph

### A part of the original graph.

2

## Degree/Valency/Order

### he number of arcs incident to a vertex/node.

3

## Path

### A finite sequence of edges such that the end vertex of one edge is the start of the next. No vertex appears more than once.

4

## Walk

### A path which you are permitted to return to vertices more than once.

5

## Cycle

### A closed path where the end vertex of the last edge is the start vertex of the first edge.

6

## Connected Graph

### A graph where all vertices are connected.

7

## Simple Graph

### Has no loop and has no more than one edge connecting each pair of vertices.

8

## Loop

### Starts and finishes at the same vertex.

9

## Digraph

### The edges have a direction associated to it.

10

## Adjacency matrix

### Records the number of direct links between vertices.

11

## Distance matrix

### Records the weights on the edges. Where there is no edge, we write "-".

12

## A Tree

### A connected graph with no cycles.

13

## A spanning tree

### A subgraph that is a tree and includes all vertices.

14

## Bipartite graph

### Two sets of verticies, X and Y. The edges only join vertices in X to vertices in Y, not to any vertices within another set.

15

## Complete graph

### Every vertex is directly connected by an edge to each of the other vertices. Denoted by K_n.

16

## Complete bipartite graph

### Denoted by K_(r,s) where there are "r" vertices in set X and "s" vertices in set Y.

17