Discrete Mathematics/Graph theory

Discrete Mathematics
 ← Enumerations Graph theory Recursion → 

Introduction

edit

A graph is a mathematical way of representing the concept of a "network".

A network has points, connected by lines. In a graph, we have special names for these. We call these points vertices (sometimes also called nodes), and the lines, edges.

Here is an example graph. The edges are red, the vertices, black.

 

In the graph,   are vertices, and   are edges.

Definitions of graph

edit

There are several roughly equivalent definitions of a graph. Set theory is frequently used to define graphs. Most commonly, a graph   is defined as an ordered pair  , where   is called the graph's vertex-set and   is called the graph's edge-set. Given a graph  , we often denote the vertex—set by   and the edge—set by  . To visualize a graph as described above, we draw   dots corresponding to vertices  . Then, for all   we draw a line between the dots corresponding to vertices   if and only if there exists an edge  . Note that the placement of the dots is generally unimportant; many different pictures can represent the same graph.

Alternately, using the graph above as a guide, we can define a graph as an ordered triple  :

  • a set of vertices, commonly called V
  • a set of edges, commonly called E
  • a relation   that maps to each edge a set of endpoints, known as the edge-endpoint relation. We say an edge   is incident to a vertex   iff  .

In the above example,

  • V={v1, v2, v3, v4}
  • E={e1, e2, e3, e4, e5}
  • f such that e1 maps to {v1, v2}, e2 maps to {v1, v3}, e3 maps to {v1, v4}, e4 maps to {v2, v4}, and e5 maps to {v3, v4}.

If   is not injective — that is, if   such that   — then we say that   is a multigraph and we call any such edges   multiple edges. Further, we call edges   such that   loops. Graphs without multiple edges or loops are known as simple graphs.

Graphs can, conceivably, be infinite as well, and thus we place no bounds on the sets V and E. We will not look at infinite graphs here.

Directions, Weights, and Flows

edit

We define a directed graph as a graph such that   maps into the set of ordered pairs   rather than into the family of two-element sets  . We can think of an edge   such that   as 'pointing' from   to  . As such we would say that   is the tail of edge   and that   is the head. This is one of the vagaries of graph theory notation, though. We could just as easily think of   as the head and   as the tail. To represent a directed graph, we can draw a picture as described and shown above, but place arrows on every edge corresponding to its direction.

In general, a weight on a graph   is some function  .

A flow   is a directed graph   paired with a weight function such that the weight "going into" any vertex is the same amount as the weight "going out" of that vertex. To make this more formal, define sets

  •  
  •  

Then, formally stated, our requirement on the weight function is  

Algebraic Graph Theory

edit

While set theory is frequently used when discussing graphs, other approaches can simplify certain operations. A set can be defined using an adjacency matrix   where element   is a 1, if there is an edge between vertex i and vertex j and 0 otherwise.

Special Graphs

edit
 
The complete graph on 6 vertices

Some graphs occur frequently enough in graph theory that they deserve special mention. One such graphs is the complete graph on n vertices, often denoted by Kn. This graph consists of n vertices, with each vertex connected to every other vertex, and every pair of vertices joined by exactly one edge. Another such graph is the cycle graph on n vertices, for n at least 3. This graph is denoted Cn and defined by V := {1,2,..,n} and E := {{1,2},{2,3}, ..., {n-1,n},{n,1}}. Even easier is the null graph on n vertices, denoted Nn; it has n vertices and no edges! Note that N1 = K1 and C3 = K3.

Some Terms

edit

Two vertices are said to be adjacent if there is an edge joining them. The word incident has two meanings:

  • An edge e is said to be incident to a vertex v if v is an endpoint of e.
  • Two edges are also incident to each other if both are incident to the same vertex.

Two graphs G and H are said to be isomorphic if there is a one-to-one function from (or, if you prefer, one-to-one correspondence between) the vertex set of G to the vertex set of H such that two vertices in G are adjacent if and only if their images in H are adjacent. (Technically, the multiplicity of the edges must also be preserved, but our definition suffices for simple graphs.)

Subgraphs

edit
 
Generated Subgraphs

A subgraph is a concept akin to the subset. A subgraph has a subset of the vertex set V, a subset of the edge set E, and each edge's endpoints in the larger graph has the same edges in the subgraph. A

A subgraph   of   is generated by the vertices { }  if the edge set of   consists of all edges in the edge set of   that joins the vertices in  { }.

A path is a sequence of edges   such that ei is adjacent to ei+1 for all i from 1 to N-1. Two vertices are said to be connected if there is a path connecting them.


Trees and Bipartite Graphs

edit

A tree is a graph that is (i) connected, and (ii) has no cycles. Equivalently, a tree is a connected graph with exactly   edges, where there are   nodes in the tree.

A Bipartite graph is a graph whose nodes can be partitioned into two disjoint sets U and W such that every edge in the graph is incident to one node in U and one node in W. A tree is a bipartite graph.

A complete bipartite graph is a bipartite graph in which each node in U is connected to every node in W; a complete bipartite graph in which U has   vertices and V has   vertices is denoted  .

Adjacent,Incident,End Vertices

Self loops,Parallel edges,Degree of Vertex

Pendant Vertex : Vertex Degree one "Pendant Vertex" Isolated Vertex : Vertex Degree zero "Isolated Vertex"

Hamiltonian and Eulerian Paths

edit

Hamiltonian Cycles: A Hamiltonian Cycle received its name from Sir William Hamilton who first studied the travelling salesman problem. A Hamiltonian cycle is a path that visits every vertex once and only once i.e. it is a walk, in which no edge is repeated (a trail) and therefore a trail in which no vertex is repeated (a path). Note also it is a cycle, the last vertex is joined to the first.

A graph is said to be Eulerian if it is possible to traverse each edge once and only once, i.e. it has no odd vertices or it has an even number of odd vertices (semi-Eulerian). This has implications for the Königsberg problem. It may be easier to imagine this as if it is possible to trace the edges of a graph with a pencil without lifting the pencil off the paper or going over any lines.

Planar Graphs

edit

A planar graph is an undirected graph that can be drawn on the plane or on a sphere in such a way that no two edges cross, where an edge   is drawn as a continuous curve (it need not be a straight line) from u to v.

Kuratowski proved a remarkable fact about planar graphs: A graph is planar if and only if it does not contain a subgraph homeomorphic to   or to  . (Two graphs are said to be homeomorphic if we can shrink some components of each into single nodes and end up with identical graphs. Informally, this means that non-planar-ness is caused by only two things—namely, having the structure of   or   within the graph).

Coloring Graphs

edit

A graph is said to be planar if it can be drawn on a plane in such way that no edges cross one another except of course for meeting at vertices

Each term, the Schedules Office in some university must assign a time slot for each final exam. This is not easy, because some students are taking several classes with finals, and a student can take only one test during a particular time slot. The Schedules Office wants to avoid all conflicts, but to make the exam period as short as possible.

We can recast this scheduling problem as a question about coloring the vertices of a graph. Create a vertex for each course with a final exam. Put an edge between two vertices if some student is taking both courses. For example, the scheduling graph might look like this: Next, identify each time slot with a color. For example, Monday morning is red, Monday afternoon is blue, Tuesday morning is green, etc.

Assigning an exam to a time slot is now equivalent to coloring the corresponding vertex. The main constraint is that adjacent vertices must get different colors; otherwise, some student has two exams at the same time. Furthermore, in order to keep the exam period short, we should try to color all the vertices using as few different colors as possible. For our example graph, three colors suffice: red, green, blue.

The coloring corresponds to giving one final on Monday morning (red), two Monday afternoon (blue), and two Tuesday morning (green)...

K Coloring

edit

Many other resource allocation problems boil down to coloring some graph. In general, a graph G is kcolorable if each vertex can be assigned one of k colors so that adjacent vertices get different colors. The smallest sufficient number of colors is called the chromatic number of G. The chromatic number of a graph is generally difficult to compute, but the following theorem provides an upper bound:

Theorem 1. A graph with maximum degree at most k is (k + 1)colorable.


Proof. We use induction on the number of vertices in the graph, which we denote by n. Let P(n) be the proposition that an nvertex graph with maximum degree at most k is (k + 1)colorable. A 1 vertex graph has maximum degree 0 and is 1colorable, so P(1) is true.

Now assume that P(n) is true, and let G be an (n + 1)vertex graph with maximum degree at most k. Remove a vertex v, leaving an nvertex graph G . The maximum degree of G is at most k, and so G is (k + 1)colorable by our assumption P(n). Now add back vertex v. We can assign v a color different from all adjacent vertices, since v has degree at most k and k + 1 colors are available. Therefore, G is (k + 1)colorable. The theorem follows by induction.

Weighted Graphs

edit

A weighted graph associates a label (weight) with every edge in the graph. Weights are usually real numbers, and often represent a "cost" associated with the edge, either in terms of the entity that is being modeled, or an optimization problem that is being solved.

Discrete Mathematics
 ← Enumerations Graph theory Recursion →