动手学图深度学习task2
第二章：图理论基础
图的背景
图论中著名问题：柯尼斯堡七桥问题
-
问题：
当时东普鲁士柯尼斯堡，市区跨普列戈利亚河两岸，河中心有两个小岛。小岛与河的两岸有七条桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？ -
解决思路：
将问题简化为平面上点与线的组合，每一座桥视为一条线，桥所连接的地区视为点，从某点出发后最后再回到这点，则这一点的线数必须是偶数。 -
最终解决的法则：
对于一个给定的连通图，如果存在超过两个的奇顶点，那么满足要求的路线便不存在了，且有n个奇顶点的图至少需要\(\lceil \frac{n}{2} \rceil\)笔画出，如果只有两个即顶点，则可从其中任何一地出发完成一幅画。若所有点均为偶顶点，则从任何一点出发，所求的路线都能实现。
图的定义
-
图被记为\(G = {V, E}\)：
其中\(V = {v_1, ... , v_N}\)是数量为\(N = |V|\)的节点(node/vertex)的集合。
\(E = {e_1, ... , e_M}\)是数量为\(M\)的边(edge/link)的集合。 -
图用节点表示实体(entities)，用边表示实体间的关系(relations)。
-
假如一条边\(e \in E\)连接两个节点\(v_1\)和\(v_2\)，那么这条边可以表示为\(e = (v_1, v_2)\)。
-
节点和边的信息可以是类别型(categorical)的，取值是那一类别，其信息称为标签(label)；也可以是数值型(numeric)的，取值范围为实数，其信息称为属性(attribute)。
-
在图的计算任务中，通常认为节点一定含有信息（至少含有节点的度的信息），边能含有信息。
-
图可以根据边是否具有指向性分为两类：
- 有向图(directed graph / digraph)：有向图的边具有指向性。
- 无向图(undirected graph)：无向图的边不具备指向性。
-
图可以根据边是否具有关联的数值(权重)分为两类：
- 有权图(weighted graph)：每条边都有权重、权重可以代表两个节点之间距离、连接强度、成本等任何有意义的量，且有权图边通常包括两个节点和它们的权重，例如\((v_A, v_B, 5)的权重记为w_{ij}\)。
- 无权图(unweighted graph)：边无权重(在应用中所有边权重相同也可认为是无权图)，边通常值包括两个节点之间存在一条边。
-
创建图的示例：
# 创建一个图（无向无权图(权重默认为1)） g = nx.Graph() # 添加图的节点 g.add_node(2) g.add_node(5) # 添加图的边 g.add_edge(2, 5, weight=4) # 图转变为有权图 g.add_edge(1, 4) # 所需节点不存在时，自动创建相应的节点 g.add_edge(1, 2) g.add_edge(2, 6) # 绘制图，默认无权重显示 nx.draw(g) # 创建有向图： h = nx.DiGraph() # 判断是否有向： >>> g.is_directed() #输出False
图的性质
以下示例均以networkx中自带图The Karate Club Network为例
G = nx.karate_club_graph()。