igraph 参考手册

用于使用 igraph C 库

第 18 章。图着色

1. igraph_vertex_coloring_greedy — 使用贪婪算法计算顶点着色。
2. igraph_coloring_greedy_t — 贪婪图着色的排序启发式算法。
3. igraph_is_perfect — 检查图是否是完美图。

1. `igraph_vertex_coloring_greedy` — 使用贪婪算法计算顶点着色。

igraph_error_t igraph_vertex_coloring_greedy(const igraph_t *graph, igraph_vector_int_t *colors, igraph_coloring_greedy_t heuristic);

此函数为图的每个顶点分配一种“颜色”——表示为非负整数——使得相邻的顶点永远不会有相同的颜色。获得的着色不一定是最小的。

顶点被贪婪地着色，一个接一个，总是选择与已着色邻居的颜色不同的最小颜色索引。顶点以由指定的启发式算法确定的顺序选择。颜色由非负整数 0, 1, 2, ... 表示

参数：

`图`:	输入图。
`colors`:	指向已初始化的整数向量的指针。顶点颜色将存储在此处。
`heuristic`:	在贪婪着色期间使用的顶点排序启发式算法。有关更多信息，请参阅 `igraph_coloring_greedy_t`。

返回值：

错误代码。

示例 18.1。文件 examples/simple/igraph_coloring.c

#include <igraph.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t colors;

    /* Setting a seed makes the result of erdos_renyi_game_gnm deterministic. */
    igraph_rng_seed(igraph_rng_default(), 42);

    /* IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS are both equivalent to 0/FALSE, but
       communicate intent better in this context. */
    igraph_erdos_renyi_game_gnm(&graph, 1000, 10000, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

    /* As with all igraph functions, the vector in which the result is returned must
       be initialized in advance. */
    igraph_vector_int_init(&colors, 0);
    igraph_vertex_coloring_greedy(&graph, &colors, IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS);

    /* Verify that the colouring is valid, i.e. no two adjacent vertices have the same colour. */
    {
        igraph_integer_t i;
        /* Store the edge count to avoid the overhead from igraph_ecount in the for loop. */
        igraph_integer_t no_of_edges = igraph_ecount(&graph);
        for (i = 0; i < no_of_edges; ++i) {
            if ( VECTOR(colors)[ IGRAPH_FROM(&graph, i) ] == VECTOR(colors)[ IGRAPH_TO(&graph, i) ]  ) {
                printf("Inconsistent coloring! Vertices %" IGRAPH_PRId " and %" IGRAPH_PRId " are adjacent but have the same color.\n",
                       IGRAPH_FROM(&graph, i), IGRAPH_TO(&graph, i));
                abort();
            }
        }
    }

    /* Destroy data structure when we are done. */
    igraph_vector_int_destroy(&colors);
    igraph_destroy(&graph);

    return 0;
}

2. `igraph_coloring_greedy_t` — 贪婪图着色的排序启发式算法。

typedef enum {
    IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS = 0,
    IGRAPH_COLORING_GREEDY_DSATUR = 1
} igraph_coloring_greedy_t;

igraph_vertex_coloring_greedy() 的排序启发式算法。

值：

`IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS`:	选择已着色邻居数量最多的顶点。
`IGRAPH_COLORING_GREEDY_DSATUR`:	选择在其邻域中具有最多唯一颜色的顶点，即其“饱和度”。当多个顶点具有相同的饱和度时，选择尚未着色的邻居最多的顶点。在 igraph 0.10.4 中添加。此启发式方法被称为“DSatur”，由 Daniel Brélaz 提出：为图的顶点着色的新方法，Commun. ACM 22, 4 (1979), 251–256. https://doi.org/10.1145/359094.359101

3. `igraph_is_perfect` — 检查图是否是完美图。

igraph_error_t igraph_is_perfect(const igraph_t *graph, igraph_bool_t *perfect);

完美图是一个无向图，其中每个诱导子图的色数等于该子图的最大团的阶数。图 G 的色数是对 G 的顶点进行着色所需的最小颜色数，以便没有两个相邻的顶点共享相同的颜色。

警告：此函数可能会在内部创建图的补图，这会消耗大量内存。对于中等大小的图，请考虑将它们分解为双连通分量，并在每个分量上单独运行检查。

此实现基于强完美图定理，该定理由 Claude Berge 推测，并由 Maria Chudnovsky、Neil Robertson、Paul Seymour 和 Robin Thomas 证明。

参数：

`图`:	输入图。预计它是无向的和简单的。
`perfect`:	指向整数的指针，结果将存储在此处。

返回值：

错误代码。

时间复杂度：最坏情况下是指数级的，但在实践中通常更快。

igraph 参考手册

第 18 章。 图着色

1. igraph_vertex_coloring_greedy — 使用贪婪算法计算顶点着色。

2. igraph_coloring_greedy_t — 贪婪图着色的排序启发式算法。

3. igraph_is_perfect — 检查图是否是完美图。

第 18 章。图着色

1. `igraph_vertex_coloring_greedy` — 使用贪婪算法计算顶点着色。

2. `igraph_coloring_greedy_t` — 贪婪图着色的排序启发式算法。

3. `igraph_is_perfect` — 检查图是否是完美图。