A graph which has numbers associated with each edge

2 of 26

Subgraph

Part of the original graph, G, whose nodes and arcs belong to G

3 of 26

Valency

The number of arcs incident to the node

4 of 26

Path

A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once

5 of 26

Cycle

A closed 'path', i.e. the end vertex of the last edge is the start vertex of the first edge

6 of 26

Walk

A path which you are allowed to return to vertices more than once

7 of 26

Connected graph

Two vertices are connected if there is an arc between them. A graph is connected if all its vertices are connected

8 of 26

Loop

An edge that starts and finishes at the same vertex

9 of 26

Simple graph

One in which there are no loops and they don't have more than one edge connecting any pair of vertices

10 of 26

Digraph

If the edges of a graph have a direction associated with them they are known as directed edges and the graph is a digraph

11 of 26

Tree

A connected graph with no cycles

12 of 26

Spanning tree

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

13 of 26

Bipartite graph

Consists of two sets of vertices, X and Y. The edges only join vertices in X with vertices in Y, not vertices within a set

14 of 26

Complete graph

A graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices, then the connected graph is denoted by Kn

15 of 26

Complete bipartite graph

A bipartite graph such that every pair of vertices in the two sets are adjacent

16 of 26

Isormorphic graphs

Graphs that show the same information but are drawn differently

17 of 26

Adjacency matrix

A matrix which records the number of direct links between vertices

18 of 26

Distance matrix

A matrix which records the weights on the edges of a weighted graph

19 of 26

Algorithm

A precise set of instructions so clear that anyone can use them to achieve a particular goal in a specified number of steps

20 of 26

Traversible (Eulerian) graph

A graph in which every vertex is even, making it possible to traverse every arc once and return to the start vertex

21 of 26

Semi-traversible (Semi-Eulerian) graph

A graph with precisely two odd vertices, making it possible to traverse every arc once, provided you start and finish at the odd vertices

22 of 26

A non-traversible graph

A graph with more than two odd vertices

23 of 26

Matching

A one to one pairing of some or all of the nodes of one set in a bipartite graph with nodes of the alternate set. One to one means each node from one set is matched with only one node from the alternate set

24 of 26

Maximal matching

A matching in which the number of arcs is as big as possible

25 of 26

Complete matching

A matching in of two sets, each containing n nodes, which has n arcs

26 of 26

Other cards in this set

Card 2

Front

A graph which has numbers associated with each edge

Back

Weighted graph/network

Card 3

Front

Part of the original graph, G, whose nodes and arcs belong to G

Back

Card 4

Front

The number of arcs incident to the node

Back

Card 5

Front

A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once

## Comments

No comments have yet been made