图论初步

---

（由于技能树点歪了，所以本篇有很多额外补充内容owo)

对于图G

① G = {V(G),E(G)}
② 节点集 记为: V(G)
③ 边集 记为: E(G)

---

∀ G = （V,E) |V| = P, |E| = q 则称G为（p,q)图

G = (V,E) , H = (U,F) 若要使G = H，则要使V = U,E = F

G（1，0） —–平凡图

G（p，0） —–零图

---

图 G=(V, E) 由下列要素构成：

• 一组节点（也称为 verticle）V=1,…,n
• 一组边 EV×V边 (i,j) ∈ E 连接了节点 i 和 j
• i 和 j 被称为相邻节点（neighbor
• 节点的度（degree）是指相邻节点的数量

偶图与奇图

若无向图G = <V,E>的结点集V能够划分为两个子集V1,V2，满足V1∩V2 = F(空集)，且V1∪V2 = V（全集），使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图（Bipartite Graph）或二分图（Bigraph）。

奇图(odd graph)一类重要的图.它是交不邻图.设S为2k-1个元素组成的集合，取S的所有k一1元素的子集为节点，若这样的两子集不相交，相应的两顶点连以边，则这样构成的图称为奇图，记为Ok. 。

---

额外补充: 自反与反自反

反自反关系(anti-reflexive relation)是一种特殊的关系，指任何事物与其自身之间都不具有的那种关系。用符号表示：R是A上的反自反关系⇔∀a(a∈A→¬(aRa))。当A上的R为反自反关系时，称R在A上是反自反的，或说A上的关系R有反自反性。例如，整数集上的关系R={〈x，y〉|x大于y}是反自反的，又如人群中关系G={〈x，y〉|x是y的父亲}是反自反的。一个关系不能既是自反的又是反自反的，但存在既不是自反的又不是反自反的关系。如A={a，b}上的二元关系R={〈a，a〉，〈a，b〉}。当A上的关系R是反自反的时，A的矩阵的主对角线上的元素全为0。

自反的关系亦称“具有反身性的关系”。对于类K中一个确定的关系R来说，若类K中任意的个体和它自身都具有关系R，则称关系R在类K中为自反的关系。若类K中没有一个个体和它自己具有关系R，则称关系R在类K中为反自反的关系。若类K中有的个体和它自己具有关系R，而有的个体和它自己不具有关系R，则称关系R在类K中为非自反的**关系**。例如，设类K为实数域，则等于关系“=”是自反的关系，大于关系“>”，小于关系“<”都是反自反的关系。“x的平方数是Y”的这种关系就是非自反的关系。因为0的平方数是0，1的平方数是1，即当x为0(或1)时，y也同时为0(或1)，但当x为其它实数时，x的平方数y就不能再与x相同了。所以，“x的平方数是y”的这种关系就既不是自反的关系，也不是反自反的关系，而是非自反的关系。

---

额外补充: 二元关系

数学上，二元关系用于讨论两个数学对象的联系。诸如算术中的「大于」及「等于」，几何学中的”相似”，或集合论中的”为…之元素”或”为…之子集“。二元关系有时会简称关系，但一般而言关系不必是二元的。

关系

关系的性质主要有以下五种：自反性，反自反性，对称性，反对称性和传递性。

自反性：

在集合X上的关系R，如对任意

)有

则称R是自反的

反自反性（自反性的否定的强形式）：

在集合X上的关系R，如对任意

)，有

则称R是反自反的。

对称性：

在集合X上的关系R

如果有 则必有

则称R是对称的。

反对称性（不是对称性的否定）：

非对称性（对称性的否定的强形式）：

非对称关系是满足反自反性的反对称关系。

传递性：

---

邻接矩阵

定义

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵：

①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

---

特点

无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+…+(n-1)=n(n-1)/2个单元。

无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。

有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。

用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。

---

描述

int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < G->n;i++) //读入顶点信息，建立顶点表
{
    G->vexs[i]=getchar();
}
for(i = 0;i < G->n;i++)
{
    for(j = 0;j < G->n;j++)
    {
        G->edges[i][j] = 0; //邻接矩阵初始化
    }
}
for(k = 0;k < G->e;k++)
{//读入e条边，建立邻接矩阵
    scanf("%d%d%d"，&i，&j，&w); //输入边(v i ,v j )上的权w
    G->edges[i][j]=w;
}
}//CreateMGraph