D1 Definitions - Graphs and Networks

• Created by: Cam
• Created on: 21-05-15 17:56
Graph
Vertices (nodes) connected by Edges (arcs).
1 of 17
Subgraph
A part of a graph.
2 of 17
Weighted Graph
Graph in which there is a number (weight) associated with each edge.
3 of 17
Valency
Number of edges a vertex has.
4 of 17
Path
Finite sequence of edges, moving from one vertex to the next.
5 of 17
Walk
Path where vertices can be visited more than once.
6 of 17
Cycle
Closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.
7 of 17
Loop
An edge that starts and finishes at the same vertex.
8 of 17
Simple Graph
Graph with no loops, one edge per vertex.
9 of 17
Digraph
A graph in which the edges have a direction associated with them - the edges are known as directed edges.
10 of 17
Tree
A connected graph with no cycles.
11 of 17
Spanning Tree
Subgraph which includes all vertices, and is a tree.
12 of 17
Bipartite Graph
Graph consisting of two sets of vertices, X and Y - X vertices only join Y vertices and vice versa.
13 of 17
Complete Graph
Every vertex is directly connected to each of the other vertices.
14 of 17
Isomorphic Graph
Same information as another graph, but drawn differently.
15 of 17
Record of no. of direct links between vertices
16 of 17
Distance Matrix
Record of weights on edges.
17 of 17

Other cards in this set

Card 2

Front

A part of a graph.

Subgraph

Card 3

Front

Graph in which there is a number (weight) associated with each edge.

Back Card 4

Front

Number of edges a vertex has.

Back Card 5

Front

Finite sequence of edges, moving from one vertex to the next.

Back 