Latest revision as of 08:14, 20 May 2013

MA375: Lecture Notes

Fall 2008, Prof. Walther

Graphs

Definition: A graph is a collection of things (usually called vertices) together with a collection of pairs of vertices (called edges)

Note: Edges are NOT geometric => no specific shape, form length

Graphs can/do have many different visualization

A simple graph is the one without loops, without multiple edges.

The degree of a vertex, deg(v) = 2 x # of loops based at v + 1 x # of nonloop edges involving v

For an undirected graph, G, with n vertices, $ \sum_{i=0}^ndeg(v_i)=2E $

--Jniederh 00:08, 3 November 2008 (UTC)

Def: Given G with vertices v_1,...., v_k edges {e_ij)an edge between v_i and v_j, then the adjency matrix A is the square k X k matrix whose i-j-entry is # of edges from v_i to v_j

Special Types of Graphs:

k-regular graphs (every vertex has degree k)

Complete graphs (K_n)

Cycles (C_n - polygon with n edges/vertices)

Wheels (W_n - C_n plus a new vertex linked to all vertices of C_n)

Bipartite Graphs (G is bipartite if the vertex set can be split into V_1 and V_2 such that all edges of G to from V_1 to V_2)

Complete Bipartite Graphs (A bipartite graph where every vertex in V_1 is connected to every vertex in V_2 without loops nor multiple edges)

Hand-Shake Theorem

Thm: Let G be an undirected graphs. Then $ \sum_{i=0}^ndeg(v_i)=2E $ because:

e_i_j counts once in deg(v_i) and deg(v_j) and

e_i_i counts twice in deg(v_i)

Euler Circuits and paths

An Euler circuit in a graph G is a simple circuit containing every edge of G. An Euler path in a graph G is a simple path containing every edge of G.

Hamiltonian Circuits and paths

A simple path in a graph G that passes every vertex exactly once is called a Hamiltonian path.

A simple circuit in a graph G that passes through every vertex at least once is called a Hamiltonian ciruit.

Back to MA375, Fall 2008, Prof. Walther