Graph Theory Origins

The Seven Bridges of Konigsberg is a milestone in the development of graph theory. Euler proved that such a path does not exist.

Euler Path/Circuit Determination Conditions

Undirected Graph

  1. Connectivity: The graph must be connected
  2. Number of odd-degree vertices:
    • 0 odd-degree vertices = Euler circuit
    • 2 odd-degree vertices = Euler path

Directed Graph

  1. Weakly connected: After ignoring edge directions, the graph is connected
  2. In-degree/out-degree balance:
    • All equal = Euler circuit
    • 1 with out-degree 1 higher + 1 with in-degree 1 higher = Euler path

Graphs and Nodes

A graph is a nonlinear data structure composed of a set of nodes and edges connecting these nodes.

Nodes

  • Unique identifier
  • Multiple property key-value pairs
  • Optional type labels

Edges

  • Directionality (directed or undirected)
  • Relationship type
  • Own properties

Knowledge Graph

A knowledge graph is essentially a data organization form based on graph structure:

  1. Nodes: Represent entities
  2. Edges: Represent relationships between entities

Graph Database

Graph databases are suitable for representing many-to-many relationships, more intuitive and flexible than relational databases.

Python NetworkX Example

# Undirected graph determination
python euler_checker.py --undirected "A-B,B-C,C-D,D-A"

# Directed graph determination
python euler_checker.py --directed "A->B,B->C,C->A"

Determination Conditions

  • Undirected graph: Connectivity + Number of odd-degree vertices (0 = Euler circuit, 2 = Euler path)
  • Directed graph: Weak connectivity + In/out-degree balance (all equal = Euler circuit, 1 with out-degree 1 higher + 1 with in-degree 1 higher = Euler path)