D1 Glossary

HideShow resource information
• Created by: Monikak
• Created on: 25-05-16 12:36
Graph
Set of vertices/nodes connected by arcs/edges.
1 of 14
Subgraph of G
A graph, each of whose vertices and edges belongs to G.
2 of 14
Weighted graph/Network
If a graph has a weight associated with each of its edges.
3 of 14
Degree of a vertex
Number of edges incident to the vertex.
4 of 14
Path
Finite sequence of edges such that the end vertex of one edge is the start vertex of the next edge. No vertex appears more than once!
5 of 14
Cycle
Closed path. Start vertex of the first edge is the end vertex of the last edge.
6 of 14
Connected
Two vertices are connected if there's a path between them.
7 of 14
Diagraph
A graph whose edges have a direction associated with them
8 of 14
Tree
Connected graph with no cycles
9 of 14
Spanning tree
Subgraph which includes all the vertices of G and is also a tree
10 of 14
Minimum spanning tree
Spanning tree such that the total length of its arcs is as small as possible
11 of 14
Bipartite graph
Consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y
12 of 14
Matching
Pairing of some or all the elements of one set with the elements of a second set
13 of 14
Complete matching
If every member of one set, X, is paired with every member of set Y
14 of 14

Other cards in this set

Card 2

Front

A graph, each of whose vertices and edges belongs to G.

Subgraph of G

Card 3

Front

If a graph has a weight associated with each of its edges.

Card 4

Front

Number of edges incident to the vertex.

Card 5

Front

Finite sequence of edges such that the end vertex of one edge is the start vertex of the next edge. No vertex appears more than once!