图论起源

柯尼斯堡七桥问题是图论发展史上的里程碑事件。欧拉证明了不存在这样的路径。

欧拉路径/回路判定条件

无向图

  1. 连通性：图必须是连通图
  2. 奇度顶点数量：
    • 0个奇度顶点 = 欧拉回路
    • 2个奇度顶点 = 欧拉路径

有向图

  1. 弱连通：忽略边方向后图是连通的
  2. 入度出度平衡：
    • 全部相等 = 欧拉回路
    • 1个出度大1 + 1个入度大1 = 欧拉路径

图和节点

图是由一组节点和连接这些节点的边组成的非线性数据结构。

节点

  • 唯一标识符
  • 多个属性键值对
  • 可选的类型标签

边

  • 方向性（有向边或无向边）
  • 关系类型
  • 自身属性

知识图谱

知识图谱本质上是一种基于图结构的数据组织形式：

  1. 节点：代表实体
  2. 边：代表实体之间的关系

图数据库

图数据库适合表示多对多的关系，比关系型数据库更直观灵活。

Python NetworkX 示例

# 无向图判定
python euler_checker.py --undirected "A-B,B-C,C-D,D-A"

# 有向图判定
python euler_checker.py --directed "A->B,B->C,C->A"

判定条件

  • 无向图：连通性 + 奇度顶点数量（0个=欧拉回路，2个=欧拉路径）
  • 有向图：弱连通 + 入度出度平衡（全部相等=欧拉回路，1个出度大1+1个入度大1=欧拉路径）