Graphs

Se basa en

Requisitos previos obligatorios, hasta el fondo: 11

Aprenderás a

• Prove the handshake lemma and Euler's criterion for Eulerian circuits.
• Prove that a tree with n vertices has n − 1 edges.
• Decide whether two small graphs are isomorphic.

Definición

• A simple graph consists of a set V of vertices and a set E of two-element subsets of V, called edges.
• A tree is a connected graph with no cycles.
• Graphs G and H are isomorphic if there is a bijection between their vertex sets that preserves adjacency in both directions.

Teorema

• Handshake lemma: the sum of the degrees of all vertices is 2|E|.
• A connected graph has an Eulerian circuit if and only if every vertex has even degree.
• A tree on n vertices has exactly n − 1 edges, and any two of its vertices are joined by a unique path.

Errores frecuentes

• Thinking a particular drawing determines the graph; very different drawings can show the same graph.
• Confusing Euler circuits (using each edge once) with Hamiltonian cycles (visiting each vertex once).

Conduce a

Descubrimientos opcionales

• Structure-preserving maps: homomorphisms and isomorphisms A graph isomorphism is a structure-preserving bijection whose inverse also preserves structure.
• Quivers and path algebras Directed graphs (quivers) give rise to path algebras, whose modules are the representations of the quiver.

Itinerarios de aprendizaje

• Computer science and formal methods

Lecturas complementarias

• J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)