代数、图算法：图基础

1. 图的基本概念
2. 图的基本属性和操作

Graph

图记为：$G=(V,E)$，$V$：图中的顶点集合，$E$：图中的边集合。

V = { a , b , c , d , e , f } ， E = { e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e 7 , e 8 , e 9 } V = \{a, b, c, d, e, f\}，E = \{e_1, e_2, e_3, e_4, e_5, e_6, e_7, e_8, e_9\} V={a,b,c,d,e,f}，E={e1​,e2​,e3​,e4​,e5​,e6​,e7​,e8​,e9​}

$e_1=(f,a)，e_2=(a,b)，e_3=(b,c)，e_4=(c,d)，e_5=(b,d)，e_6=(a,d)，e_7=(e,d)，e_8=(a,e)，e_9=(f,e)$

图的顶点数：order,图的边数：size.

• $G^{\prime }sorder$: 6
• $G^{\prime }ssize$: 9

补图：$G=(V,E),\bar{G}=(V,E^{\prime })$, $(u,v)\in E,(u,v)\notin E^{\prime }$

​

​

顶点的度：经过顶点$v$边的数量，记为：$deg(v)$，图中最大的度记为：$\Delta (G)$，最小的度记为：$\delta (G)$,顶点数为：$n$。满足下面关系：

$$0\le \delta (G)\le deg(v)\le \Delta (G)\le n-1$$

• 孤立顶点(isolated): 度为0的顶点。
• 垂点(pendant)：度为1的顶点。

图的度和边的关系：$m$为图中的边数。

$$\sum _{v\in V}deg(v)=2m$$

图的度序列：给定一个简单图$G$,其顶点$v_1,v_2,\cdots v_n$的度依次为：$d_1,d_2,\cdots d_n$，$D=d_1\cdots d_n$即为图的度序列。度序列非递增或递减序列，如果$D$为某个图的都序列，序列$D$被称作可图的(Graphic)。同构的图具有相同的度序列，但是度序列相同的图不一定同构。

子图：给定一个图$G=(V,E)$，$G$的子图的顶点集来自$G$顶点子集,边也是$G$的边子集。子图记为：$G^{\prime }=(V^{\prime },E^{\prime })，V^{\prime }\subseteq V，E^{\prime }\subseteq E$:

• $G^{\prime }\ne G$: $G^{\prime }$被称为$G$的真子图(proper subgraph)。
• $E^{\prime }=E$: $G^{\prime }$被称为$G$的诱导子图(induced subgraph)。
• $V^{\prime }=V$：$G^{\prime }$被称为$G$的生成子图(spanning subgraph),$G$被称为$G^{\prime }$的生成超图。

Grpah Ops

1. union : $G_1=(V_1,E_1)，G_2=(V_2,E_2)$，$G_3=union(G_1,G_2)=(V_3,E_3)$，$V_3=V_1\cup V_2，E_3=E_1\cup E_2$。
2. intersection: $G_3=intersection(G_1,G_2)=(V_3,E_3)$，$V_3=V_1\cap V_2，E_3=E_1\cap E_2$。 ($V_1\cap V2\ne \varnothing$)
3. cartesian product : $G_3=G_1\times G_3=(V_3,E_3)$，$V_3=V_1\times V_2$。

例如： { u , x } ∈ V 1 , { v , y } ∈ V 2 ， ( < u , v > , < x , y > ) ∈ E 3 \{u,x\} \in V_1, \{v, y\} \in V_2，(<u, v>, <x, y>) \in E_3 {u,x}∈V1​,{v,y}∈V2​，(<u,v>,<x,y>)∈E3​ 意味着：

$\exists (u,x)\in E_{1}or(v,y)\in V_2$

union & intersection

cartesian product

​

Types of Graphs

1. 有向图(Digraph)

​

2. 完全图：完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。
   • $n$ : 完全图的order，顶点数。
   • $n(n-1)/2$ : 图的size。

​

​

3. 加权图：$G(V,E,w)$，边加权$w:E$，点加权$w:V$

​

4. 二部图(bipartite grpahs)：

$G=(V,E)$是一个无向图，如果顶点V可分割为两个互不相交的子集$(A,B)$，并且图中的每条边$（i，j）$所关联的两个顶点 $i$ 和 $j$ 分别属于这两个不同的顶点集$(i\in A,j\in B)$，则称图$G$为一个二分图。一个完全的二分图记为：$K_{p,q}$，$P$:是第一个顶点集的顶点数量，$q$是另一个。

• 简单二部图
• 有向二部图
• 完全二部图

5. 正则图(regular graph)：正则图中每个顶点具有相同的度。正则的有向图也必须满足更多的条件，即每个顶点的出入度都要彼此相等。具有 $k$ 个自由度的顶点的正则图被称为 $k$ 度的k-正则图。 此外，奇数程度的正则图形将包含偶数个顶点。

6. 同构图：$G_1$和$G_2$具有相同数量的顶点和边，并且保持连通性，则他们是同构的。

Wakls,Paths,Cycles$\cdots$

​

• Walk $a\to c$(含重复的边和点) : $a\to e_0\to b\to e_2\to g\to e_2\to b\to e_1\to c$
• Trail $a\to c$(不含重复的边) : $a\to e_8\to g\to e_7\to f\to e_3\to b\to e_2\to g\to e_9\to c$
• Path $a\to c$(不含重复的点) :
  • $a\to g\to c$
  • $a\to b\to c$
  • $a\to b\to g\to c$
  • $a\to g\to b\to c$
• Cycle : $a\to c$ : $a\to b\to c\to a$
• Connectivity : 连通性,如果一个图在其包含的任何顶点对之间存在连接(可达到)，则称为连通图。
• Hamiltonian Cycle : 经过图中的顶点一次。
• Eulerian Cycle : 经过图中的边一次。
• 偏心度(eccentricity)：一个顶点v到图中任何其他顶点的最大距离称为v的偏心度。
• 图直径(diameter)：图中顶点的最大偏心度称为图的直径。
• 图半径(radius)：图中顶点的偏心度的最小值。
• 图中心(center)：图的中心是具有最小偏心度的顶点，一个图中可能有多个中心。(代表一些现实生活中的网络的图表中寻找中心是有益的，因为它有助于将共享的资源定位到消费者容易到达的地方。)