Graphs arise in many settings. The applications suggest useful concepts  and terminology about the structure of graphs.

­1.1. Example. Acquaintance relations and subgraphs. Does every set of six people contain three mutual acquaintances or three mutual strangers? Since "acquaintance" is symmetric, we model it using a simple graph with a vertex for each person and an edge for each acquainted pair. The "non acquaintance"relation on the same set yields another graph with the "complementary" set of  edges. We introduce terms for these concepts.

1.2 Definition.

The complement  of a simple graph G is the simple graph with vertex set V(G) defined by uv E E() if and only if uv  E(G). A  clique in a graph is a set of pairwise adjacent vertices. An independent set (or stable set) in a graph is a set of pairwise nonadjacent vertices.

In the graph G of Example 1.1, {u, x, y} is a clique of size 3 and {u, w} is an independent set of size 2, and these are the largest such sets.

These values reverse in the complement G , since clques become independent sets (and vice versa) under complementation. The question  in Example 1.1 asks whether it is trtle that every 6-vertex graph has a clique of size 3 or an independent set of size 3 .Deleting edge ux from G yields a 5-vertex graph having no clique or independent set of size 3.

1.3. Example.

Job assignments and bipartite graphs. We have m jobs, and n people,. but not all people are qualified for all jobs. Can we fill the jobs with qualified people? We model this using a simple graph H with vertices for the jobs and people; job j is adjacent to person p if p can do j.

Each job is to be filled by exactly one person, and each person can hold at most one of the jobs. Thus we seek m pairwise disjoint edges in H  (viewing  edges as pairs of vertices).

The use of graphs to model relations between two disjoint sets has many important applications. These are the graphs whose vertex sets can be partitioned into two independent sets; we-need a name for them.

1.4. Definition.

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets called partite sets of G.

1.5. Example.

Scheduling and graph coloring.. Suppose we must schedule Senate committee meetings into designated weekly time periods. We cannot assign two committees to the same time if they have a common member. How many different time periods do we need?

We create a vertex for each committee, with two vertices adjacent when their committees have a common member. We must assign labels (time periods)to the vertices so the endpoints of each edge receive different labels. In the graph below, we can use one label for each of the three independent sets of vertices grouped closely together. The members of a clique must receive distinct labels, so in this example the minimum number of time periods is three.

Since we are only interested in partitioning the vertices, and the labels have no numerical value, it is convenient to call them colors.

1.6. Definition.

The chromatic number of a graph G, written X(G), is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors. A graph G is k-partite if V(G) can be expressed as the union of k (possibly empty) independent sets.

This generalizes the idea of bipartite graphs, which are 2-partite. Vertices given the same color must form an independent set, so X (G) is the minimum number of independent sets needed to partition V (G). A graph is k-partite if and only if its chromatic number is at most k. We use the term "partite set"when referring to a ­et in a partition into independent sets. We study chromatic number and graph colorings. The most (in)famous problem

in graph theory involves coloring of "maps".

l.7. Example.

Maps and coloring­ Roughly speaking, a map is a partition of the plane into connected regions. Can we color the regions of every map using at most four colors so that neighboring regions have different colors?

To relate map coloring to graph coloring, we introduce a vertex for each region and an edge for regions sharing a boundary. The map question asks  whether the resulting graph must have chromatic number at most 4. The graph can be drawn in the plane without crossing edges; such graphs are planar.

The graph before Definition 1.6 is planar; that drawing has a crossing, but another drawing has no crossings. We study planar graphs in Chapter of(Planar Graphs ).

1.8. Definition.

 A path is a simple graph whose vertices can be ordered so that two vertices are adjacent if and only if they are consecutive in the, list. A cycle is a graph with an equal number of vertices and edges whose vertices can be placed around a circle so that two vertices are adjacent if and only if they appear consecutively along the circle.

Above we show a p­ath and a cycle, as demonstrated by listing the vertices in the order x, b, a, z, y. Dropping one edge from a cycle produces a path. In studying the ro­tes in road networks, we think of paths and cycles contained in the graph. Also, we hope that every vertex in the network .can be reached from every other. The next definition makes these concepts precise.

1.9 Definition.

 A sub graph of a graph G is a graph H such that V (H)  V(G) and E(H)  E(G)'and the assignment of endpoints to edges in H is the same as In G. We then write H  G and say that "G contains H". A graph G is connected if each pair of vertices in G belongs to a path; otherwise, G is disconnected.

Introduction to Graph Theory Second Edition, Douglas B. West , Indian Reprint, 2002,page(3.6)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength