# D1

version from 2015-06-08 16:23

## Section

A graphA graph G consists of points (vertices or nodes) which are connected by lines (edges or arcs).
A subgraphA subgraph of G is a graph, each of whose vertices belongs to G and each of whose edges belongs to G.
A networkIf a graph has a number associated with each edge (usually called its weight) then the graph is called a weighted graph or network
A path A path is 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.
A walk A walk is a path where you may visit vertices more than once.
A cycleA cycle (circuit) is a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.
Two vertices are connected ifTwo vertices are connected if there is a path between them.
A connected graphA graph is connected if all its vertices are connected.
DiagraphIf the edges of a graph have a direction associated with them they are known as directed edges and the graph is known as a digraph.
A treeA tree is a connected graph with no cycles.
A spanning treeA spanning tree of a graph G is a subgraph which includes all the vertices of G and is also a tree.
A minimum spanning treeA minimum spanning tree (MST) is a spanning tree such that the total length of its arcs is as small as possible. (MST is sometimes called a minimum connector.)
A complete graphA graph in which each of the n vertices is connected to every other vertex is called a complete graph.
A bipartite graphA bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set. (If there are r vertices in X and s vertices in Y then this graph is Kr,s.) A bipartite graph has two sets of nodes. Nodes of one set can only be matched to nodes of the other set.
A matchingA matching is the pairing of some or all of the elements of one set, X, with elements of a second set
An alternating pathAn Alternating Path starts at an unconnected vertex in one set and ends at an unconnected vertex in the other set
The degree or valencyThe degree or valency of a vertex is the number of edges incident to it. A vertex is odd (even) if it has odd (even) degree
A complete matching If every member of X is paired with a member of Y the matching is said to be a complete matching