Graphs Maps and Networks

Complete Graph of n vertices, K(n)

a graph with all connecting edges

Complete bipartite graph

a graph whose vertices can be divided into two disjoint sets

The complement of a graph

a graph that has the same vertices, but the edges only connect if they did not connect in the original

Vertex Coloring

assignment of colors to vertices

proper coloring

two vertices that are connected by an edge can’t have the same color

Chromatic Number

smallest amount of numbers in a proper coloring

subdivision of a graph

inserting new vertices along edges of the original graph

planar graph

a graph that can be drawn on a flat surface (like a piece of paper) without any edges crossing

faces

A face is a region bounded by edges in a planar drawing of a graph.

euler characteristic

a key concept in graph theory and topology that relates the number of vertices, edges, and faces in a planar graph. You

Genus of a surface (# of holes)

χ=V−E+F=2−2g

Flow

Actual amount that can be sent through an edge.

capacity

Maximum allowed flow on an edge.

a cut in a graph

a partition of the vertices of a graph into two disjoint sets

Kirchoff Vertex Condition

For any vertex vvv other than the source sss and the sink ttt, the total flow into vvv equals the total flow out of vvv. (in degree = outdegree)

Source

a vertex that has no in degree

sink

a vertex with no outdegrees

Dominating set

Every vertex is either in the dominating set or next to a vertex in it.

Domination number

The minimum number of vertices in a dominating set.