Graphs and Networks Terminology Flashcards Preview

D1 maths > Graphs and Networks Terminology > Flashcards

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

Isomorphic graph

Graphs that show the same information but are drawn differently.