Chapter 2 - Graphs and networks

graph

consists of points (called vertices or nodes) which are connected by lines (edges or arcs).

weighted graph or network

f a graph has a number associated with each edge (usually called its weight)

vertex

point on graph, vertices are soemtimes called nodes

edge

line segment joining vertices soemtimes called arcs

subgraph

graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph. It is part of the original graph.

degree/valency/order

number of edges incident to a vertex

even degree

If the degree of a vertex is even

walk

route through a graph along edges from one vertex to the next.

path

walk in which no vertex is visited more than once.

trail

walk in which no edge is visited more than once

cycle 

walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

hamiltonian cycle

cycle that includes every vertex.

when are 2 vertices connected

if there is a path between them.

when is a graph connected 

all its vertices are connected.

loop

an edge that starts and finishes at the same vertex.

simple graph

one in which there are no loops and there is at most one edge connecting any pair of vertices.

directed edge 

If the edges of a graph have a direction associated with them

directed graph

f the edges of a graph have a direction associated with them

eulers handshaling lemma 

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges. As a consequence, the number of odd nodes must be even.

tree

connected graph with no cycles.

spannin tree of a graph

subgraph which includes all the vertices of the original graph and is also a tree

complete graph

raph in which every vertex is directly connected by a single edge to each of the other vertices

Isomorphic graphs

graphs which show the same information but may be drawn differently.

what do entries represent in adjacency matrix

describes the number of arcs joining the corresponding vertices.

what do entries represent in distance matrix 

entries represent the weight of each arc, not the number of arcs.

planar graph

ne that can be drawn in a plane such that no two edges meet except at vertex

what can planarity alogrith m be used for

The planarity algorithm may be applied to any graph that contains a Hamiltonian cycle. It provides a method of redrawing the graph in such a way that it becomes clear whether or not it is planar.

planarity algorithm

1 Identify a Hamiltonian cycle.

2 Draw a polygon with vertices labelled to match the ones in the Hamiltonian cycle.

3 Draw edges inside the polygon to match the edges of the original graph not already represented by the polygon itself.

4.маkе а list of all edges inside the olygon in any order. 5.Choose any unlabelled edge in your list and label it 'l'. If all edges are now labelled then the graph is planar.

6.Look at any unlabelled edges that cross the edge(s) just labelled: . If there are none, then go back to step 5  If any of these edges cross each other, then the graph is non-planar. • If none of these edges cross each other, give them the opposite label to the edge(s) just labelled. If all edges are now labelled, the graph is planar. Otherwise, go back to the start of step