有限简单无向图

图把一个系统拆成“有哪些对象”和“哪些对象之间有联系”。顶点集负责保存全部对象，包括暂时没有联系的对象；边集只记录允许的成对关系。省略孤立点，会改变顶点数、连通性乃至算法输入，不能只从画出的线条反推整个图。

图画的位置、线段长度和弯曲方式通常不属于图本身。两条画线交叉，不会自动在交点产生新顶点；把顶点挪远，也不会改变它的度数。只有明确增加嵌入、距离或边权之后，这些额外数据才进入问题。

从一张小图读出结构 ​

取

前三个顶点构成三角形，$d$ 通过一条边接在 $c$ 上。邻域为 $N(a)=\{b,c\}$、$N(b)=\{a,c\}$、$N(c)=\{a,b,d\}$、$N(d)=\{c\}$，所以度数依次为 $2,2,3,1$。

按 $(a,b,c,d)$ 编号，其邻接矩阵是

读第三行时，三个 $1$ 分别位于 $a,b,d$ 对应的列，因此直接还原出 $N(c)=\{a,b,d\}$；行和就是 $c$ 的度数 $3$。读第一行第四列的 $0$，则知道 $a,d$ 没有直接边，但这没有排除经过 $c$ 的间接连接。

无向性对应矩阵对称，无自环对应对角线为零，简单性对应非对角项只有 $0$ 或 $1$。换一种顶点编号会同时置换行和列，而不是改变连接结构。

度数能说明什么 ​

每条边在两个端点各贡献一次度数，故

这就是握手恒等式。例子中左边为 $2+2+3+1=8$，恰为四条边的两倍。进一步按度数奇偶拆分总和，可知奇度顶点的个数必为偶数；“只有一个奇度顶点”的有限无向图因此不可能存在。

度数序列却不能决定整张图。六顶点环 $C_6$ 与两个互不相连的三角形，都有六个度数为 $2$ 的顶点；前者连通，后者不连通。相同的局部连接数量，不保证相同的全局路径结构。

改变模型，会改变允许的边 ​

有向图公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。把边的方向纳入数据；$u\to v$ 和 $v\to u$ 可以分别存在。多重图允许同一对端点间有不同边，需要为这些边保留各自身份。自环又会改变“度数如何贡献”的约定，不能继续把度数直接等同于不同邻居的数量。

例如 Cuckoo Hashing 的键—槽图可能有不同键对应同一对候选槽，因而自然得到多重边。这里的简单图提供基础语言，但要分析那种模型，必须保留重复边，不能把边集合去重后继续计数。类似地，给边附非负权重得到的是加权图；权重不是多重边数，零权边在组合连接与某些算子中也可能发挥不同作用。

本条的图也可视为每条超边大小都等于 $2$ 的超图公理库超图Hypergraph边可以连接任意多个顶点而非仅两个顶点的离散结构。。这一包含关系保留顶点集，因此孤立点并不会在转换时消失。

由于边只能从所有无序顶点对中选择，

达到上界的是完全图 $K_n$。这个上界依赖于简单且无自环；允许多重边后，固定顶点数不再限制总边数。

图中的路与圈公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。追踪连接如何连续延伸，连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。再把顶点划分为互相可达的部分。它们讨论的是边的组合结构，而不是画图时两点在平面上是否靠近。图与这些派生概念应分层定义，以免把“看上去是一整块”代替可达性证明。

表示会影响算法成本。邻接矩阵使用 $\mathrm{\Theta }(n^2)$ 槽位，在适当的 RAM 模型中可常数时间检查一对顶点是否相邻；邻接表使用 $\mathrm{\Theta }(n+m)$ 空间，可用 $\mathrm{\Theta }(1+d(v))$ 时间枚举某个顶点的邻居，包含空邻居表的入口检查。邻接表若未另建索引，检查指定邻居不一定是常数时间。稀疏图和稠密图适合的表示不同，不能把数学对象与某一种存储方式绑定。