什么是完美图？ | Baeldung中文网

1. Overview

In this tutorial, we’ll explore the definition of the perfect graph and its theorem in depth. Then, we’ll examine its mathematical implications and the key characteristics of perfect graphs. In addition, we’ll look at how perfect graphs are used in practice. Finally, we define the Strongly Perfect and the Weakly Perfect, which are used to classify perfect graphs.

2. What Exactly Is Graph Theory?

The study of graphs in both computer science and mathematics is known as graph theory. A graph is a mathematical structure employed to construct pairwise relationships between objects in a collection. In this context, a graph is a collection of nodes, also known as vertices, and the edges that connect them:

Graph

The graph above demonstrates this:

Graph
Vertices
Edges

3. What Are Perfect Graphs?

A graph is said to be perfect if and only if each induced subgraph of has a clique number equal to its chromatic number, in other words, $\omega(G) = \chi(G)$ . In this context, a non-perfect graph is known as an imperfect graph. Let’s study these characteristics in the following subsections.

3.1. Chromatic Number of a Graph

The least amount of colors necessary to color the vertices of a graph so that no two adjacent nodes have the same color is its chromatic number.

The chromatic number of a graph is most frequently written as $\chi(G)$ .

The graphs below show the minimal colorings and chromatic numbers for a selection of them:

chromatic number of a graph

3.2. Clique Number of a Graph

A clique is a vertex-induced subgraph of a complete graph. A set is a clique of an graph if and only if $C \subseteq V(G)$ and U,V $\in C$ and $\neq V$ $\Rightarrow$ U,V $\in E(G)$ .

A graph G’s clique number, denoted $\omega(G)$ , is the number of vertices in its maximum clique. It is equivalently the size of G’s largest clique or maximal clique.

As previously stated, a clique of a graph is a complete subgraph of . A clique is maximal if and only if it’s not a proper subgraph of another clique. A maximum clique of a graph is a clique with as many or more vertices as any other clique of .

The clique of a graph is illustrated in the graphs below, and the number of cliques for a single graph G is shown in red:

Clique Number of a Graph

3.3. The Definition of Perfect Graphs

A graph G = (V, E) is perfect graph if for all $S \subseteq V$ , $\omega(G[S]) = \chi(G[S])$ .

It means that the chromatic and clique number for each graph’s induced subgraphs must match for a graph to be considered perfect.

Let’s see some examples based on the following graphs:

perfect graph examples

Since the clique number $\omega(G)$ in a graph equals the chromatic number $\chi(G)$ , it is a perfect graph. $\omega(G) = 2$ and $\chi(G) = 2$ , so $\omega(G) = \chi(G)$

However, the chromatic number $\chi(G)$ for graph is 4, and the clique number $\omega(G)$ is 3. As a result, graph is not a perfect graph.

Let $\G = (V, E)$ be a graph. A suitable coloring of is a function from to some set , so that $\f(x) = f(y)$ whenever $\ (x, y) \in E$ . The chromatic number of is the size of the smallest set for which there exists a suitable coloring of from to .

We denote by $\omega(G)$ the largest clique’s size and by $\chi(G)$ the chromatic number of . It is true for every graph that $\omega(G) \le \chi(G)$ . It is said that a graph is perfect if, for each induced subgraph of , $\omega(G) = \chi(G)$ .

A perfect cycle with three vertices is depicted in the graph below:

perfect graph example

Cycle with 3 vertices
Chromatic number $\chi(G) = 3$
Clique number $\omega(G) = 3$

A, B, and C are cliques in this graph, and the clique number is 3. Consequently, $\omega(C3)= 3$ since $\omega(G) = \chi(G)$ . Accordingly, the clique number of graph is equal to the chromatic number of graph . As a result, the cycle graph is a perfect graph.

4. Strong Perfect Graph

A graph is strongly perfect if each induced subgraph H has a unique vertex set that satisfies each of H’s maximal cliques. Every strong perfect graph is perfect, but the opposite is not always true. The figure next presents a strong perfect graph:

strong perfect graphs

5. Weak Perfect Graph

A graph is weakly perfect if $\omega(G)=\chi(G)$ . This condition must hold for induced subgraphs to say a graph is perfect, but there is no requirement that it does. The clique number is $\omega(G)$ , and the chromatic number is $\chi(G)$ . Thus, in every situation, weak perfect graphs exist. The following example shows a weak perfect graph:

weakly perfect graphs

5. Conclusions

This article covered perfect graphs, one of the most popular graph theories. At first, we discussed the perfect graph theorem. Then, to better understand the concepts, examples were used to explain the graphs’ chromatic and clique numbers. Finally, we presented both strong perfect graphs and weak perfect graphs. Readers will consequently have a thorough understanding of perfect graphs and their potential applications.

Persistence

REST

Security