Notes
Summary of Chapter 2
Content of the notes (1)
Page 1
1 A graph consists of
vertices(nodes) which are connected by edges(arcs).
2 A subgraph is part
of a graph.
3 If a graph has a
number associated with each edge (its weight) then the graph is a weighted
graph (network).
4 The degree or
valency (or order) of a vertex is the number of edges incident to it.
5 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.
6 A walk is a path in
which you are permitted to return to vertices more than once.
7 A cycle (circuit)
is a closed ‘path’, i.e. the end vertex of the last edge is the start vertex of
the first edge.
8 Two vertices are
connected if there is a path between them. A graph is connected if all its
vertices are connected.
9 A loop is an edge
that starts and finishes at the same vertex.
10 A simple graph is
one which there are no loops and not more than one edge connecting any pair of
vertices
11 If the edges of a
graph have a direction associated with them they are known as a directed edges
and the graph is known as a digraph.
12 A tree is a
connected graph with no cycles.
13 A spanning tree of
a graph, G, is a subgraph which includes all the vertices of G and is also a
tree.
14 A 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.
15 A complete graph
is a graph in which every vertex is directly connected by an edge to each of
the other vertices. If the graph has n
vertices the connected graph is denoted kn.
16 A complete
bipartite graph (denoted kr,s) is a
graph in which there are r vertices
in set X and s vertices in set Y.
17 Isomorphic graphs
show the same information but are drawn differently.
18 An adjacency
matrix records the number of direct links between vertices.
19 A distance matrix
records the weights on the edges. Where there is no weight, this is indicated
by ‘-‘.
Page 1
Information
- Description
- Decision (Chapter 2: Graphs and networks) Note on Summary of Chapter 2, created by jakubburger on 11/04/2013.
- Created by
- jakubburger · Apr 2013
- Updated
- Aug 16, 2016
- Views
- 96
- Tags
- Rating
More on Graph Terminology and Types