Section 2

Page 1

A graph is made up of points (nodes/vertices) joined by lines (edges/arcs).

Weighted Graphs/Networks have a number on Each Arc

Digraphs/Directed Graphs have Directed Edges

Complete Graph's ertices are All Directly Connected

Subgraphs are bits of another graph

rub out bits of a graph you get a subgraph

A subgraph of graph G is a graph where all the vertices and edges belong to G

Paths are routes in the graph that don't repeat any vertices

A Path is a sequence of edges that flow on, end to end

A Cycle/Circuit is a path that brings you back to your starting point

a closed path

the end vertex is the same as the start vertex

Trees are graphs with no cycles

have to be connected graphs

Spanning Trees are subgraphs that are also trees

have to include all the vertices

the number of edges is one less than the number of vertices

The Degree of a Vertex is the number of lines coming off it

The degree/valency of a vertex (node order) is the number or edges connected to it

a vertex with an odd degree is odd, one with an even degree is even

The sum of the degrees is always double the number of edges, so it is always even.

Adjacency/Incidence Matrices show the number of links between vertices

to draw from a graph, count the number of direct connections from the vertex at the left of the row to the vertex at the top of the column

Distance Matrices show the weights between vertices

To draw, write down the weight between the two vertices, only including direct links

weights with directed edges only get written once

Graphs