Carre et Bipartition de Graphe

图的平方（G²）

定义

对于一个图 G = (V, E)，它的平方图 G² 是一个具有相同顶点集 V 的新图，其中：

• 如果 u 和 v 在原图 G 中的最短路径距离 d_G(u, v) ≤ 2，则在 G² 中添加一条边 (u, v)。

换句话说，在平方图中，原图中相邻的顶点仍然相邻，且所有原图中距离为 2 的顶点在平方图中会直接相连。

数学表示

设原图 G 的邻接矩阵为 A，则平方图 G² 的邻接矩阵 A² 可以通过矩阵乘法计算：
A² = A + A²
其中：

• A 是原图的邻接矩阵，A² 计算了两步可达的顶点对。
• A² 的非零元素表示原图中两步可达的顶点，它们会在平方图中直接相连。

下面分别对MatAdj和ListeAdj两种图的结构实现图的平方：

MatAdj

MatAdj carre_MA(MatAdj g) {
    int n = g.nbSom;
    MatAdj g2 = allocMatAdj(n);
    for (int s = 0; s < n; s++) {
        for (int t = 0; t < n; t++) {
            int u = 0;
            while (u < n && g.mat[s][u] * g.mat[u][t] == 0) {
                u++;
            }
            if (u < n) {
                g2.mat[s][t] = 1;
            } else {
                g2.mat[s][t] = 0;
            }
        }
    }
    return g2;
}

ListeAdj

// 检查链表中是否存在某个元素t
int existeDansListe(Liste l, int t) {
    while (l != NULL) {
        if (l->somSucc == t) {
            return 1;  // 存在
        }
        l = l->suiv;
    }
    return 0;  // 不存在
}

ListeAdj carre_LA(ListeAdj g) {
    int n = g.nbSom;
    int u, t;
    ListeAdj g2 = allocListeAdj(n);

    // 遍历每个顶点s
    for (int s = 0; s < n; s++) {
        Liste ls = g.tabAdj[s];  // 顶点s的邻接链表

        // 遍历s的邻接链表
        while (ls != NULL) {
            u = ls->somSucc;  // 邻接的顶点u
            ls = ls->suiv;  // 移动到u的下一个邻接顶点

            // 遍历u的邻接链表
            Liste lu = g.tabAdj[u-1];
            while (lu != NULL) {
                t = lu->somSucc;  // 邻接的顶点t
                if (!existeDansListe(g2.tabAdj[s],t)) {
                    g2.tabAdj[s] = inserTete(g2.tabAdj[s], t);  // 将t加入i的邻接链表
                }
                lu = lu->suiv;  // 移动到t的下一个邻接顶点
            }
        }
    }
    return g2;
}

测试函数

#include "Carre.h"

#include "../PrintFree.h"

int main() {
    int n = 4;
    MatAdj ma;
    ma.nbSom = n;
    ma.mat = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        ma.mat[i] = (int *)malloc(n * sizeof(int));
    }

    // 初始化矩阵（有向图不带自环）
    int adj[4][4] = {
        {0, 1, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 1},
        {1, 0, 0, 0}
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ma.mat[i][j] = adj[i][j];
        }
    }

    printMatAdj(ma);
    MatAdj g2=carre_MA(ma);
    printMatAdj(g2);

    ListeAdj la=Mat_Liste(ma);
    printListeAdj(la);
    ListeAdj g3=carre_LA(la);
    printListeAdj(g3);
}

Bipartition

判断一个图是否是二分图

C语言实现

#define MAX_SOM 100

typedef struct cel {
    int elt;
    struct cel *suiv;
} *Ensemble;


Ensemble initE() {
    Ensemble e;
    e = NULL;   // 初始化为空链表
    return e;
}

// 在链表头部插入新节点
Ensemble inserTeteE(int s, Ensemble e) {
    Ensemble newCell = malloc(sizeof(struct cel));
    if (!newCell) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newCell->elt = s;
    newCell->suiv = e;  // 让新节点指向原来的头节点
    e=newCell;      // 返回新的头节点
    return e;
}

int *initTab(int n, int *tab) {
    int i = 0;
    for (i = 0; i < n; i++) {
        tab[i] = 0;
    }
    return tab;
}



//etape1
//广度优先遍历，记录每个点的层级
int *Marquage(MatAdj g) {
    int n = g.nbSom;
    int *visite = malloc(n * sizeof(int));
    int *marquage = malloc(n * sizeof(int));
    visite = initTab(n, visite);
    marquage = initTab(n, marquage);

    int s = 0;
    int nbSV = 0;
    File *f = initFile(MAX_SOM);
    enfiler(s, f);
    marquage[s] = 0;

    while (!estVideFile(f) && nbSV < n) {
        s = sommetFile(f);
        defiler(f);
        if (visite[s] == 0) {
            visite[s] = 1;
            nbSV++;
            for (int t = 0; t < n; t++) {
                if (g.mat[s][t] == 1 && visite[t] == 0) {
                    enfiler(t, f);
                    marquage[t] = marquage[s] + 1;
                }
            }
        }
    }
    free(visite);
    return marquage;
}

//etape2 将图分为S1,S2两个集合
void partition(int n, int *marquage,Ensemble *s1,Ensemble *s2) {
    // s1=initE();
    // s2=initE();
    for (int s=n-1;s>=0;s--) {
        if (marquage[s]%2==0) {
            *s1=inserTeteE(s,*s1);
        }else {
            *s2=inserTeteE(s,*s2);
        }
    }
}

//etape3 判断S1和S2是否是连通的
int estLiaison(Ensemble S, MatAdj g) {
    int flag = 0;  // 初始化 flag，表示是否找到连接的边
    Ensemble temp1 = S;

    // 遍历集合 S 中的每一对节点
    while (temp1 != NULL && flag == 0) {  // 如果 flag 为 1，则不再继续检查
        int s = temp1->elt;
        Ensemble temp2 = temp1->suiv;

        while (temp2 != NULL) {
            int t = temp2->elt;
            // 检查节点 s 和 t 是否有边连接
            if (g.mat[s][t] == 1 || g.mat[t][s] == 1) {
                flag = 1;  // 如果有连接边，将 flag 设置为 1
                break;  // 立即退出内层循环
            }
            temp2 = temp2->suiv;
        }
        temp1 = temp1->suiv;
    }

    return flag;  // 返回 flag，1 表示有连接边，0 表示没有
}

//主函数
int estBiparti(MatAdj g) {
    int n=g.nbSom;
    int *marquage=Marquage(g);
    Ensemble s1,s2;
    s1=initE();
    s2=initE();
    partition(n,marquage,&s1,&s2);

    int biparti=!estLiaison(s1,g) && !estLiaison(s2,g);

    free(s1);
    free(s2);
    free(marquage);

    return biparti;
}

测试函数

#include "bipartition.h"

int main() {

    int n = 10;
    MatAdj ma;
    ma.nbSom = n;
    ma.mat = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        ma.mat[i] = (int *)malloc(n * sizeof(int));
    }

    int adj[10][10] = {
        {0, 1, 1, 0, 0, 0, 0, 0, 0, 0},  // 1 -> 2, 1 -> 3
        {0, 0, 0, 1, 1, 0, 0, 0, 0, 0},  // 2 -> 4, 2 -> 5
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1},  // 3 -> 10
        {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},  // 4 -> 6
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  // 5 (无出边)
        {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},  // 6 -> 7
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  // 7 (无出边)
        {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},  // 8 -> 9
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},  // 9 (无出边)
        {0, 0, 0, 0, 0, 0, 0, 1, 0, 0}   // 10 -> 8
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ma.mat[i][j] = adj[i][j];
        }
    }

    int *marquage=Marquage(ma);

    for (int i=0;i<10;i++) {
        printf("%d ",marquage[i]);
    }
    printf("\n");

    Ensemble s1,s2;
    s1=initE();
    s2=initE();
    partition(n,marquage,&s1,&s2);

    while (s1!=NULL){
        printf("%d ",s1->elt+1);
        s1=s1->suiv;
    }
    printf("\n");
    while (s2!=NULL){
        printf("%d ",s2->elt+1);
        s2=s2->suiv;
    }
    printf("\n");

    if (estBiparti(ma)) {
        printf("le graphe est biparti\n");
    }else {
        printf("le graphe n'est pas biparti\n");
    }
}