Graphs

इस पर आधारित

11 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)

आप सीखेंगे

• 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.

परिभाषा

• 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.

प्रमेय

• 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.

आम भ्रांतियाँ

• 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).

आगे ले जाता है

वैकल्पिक खोजें

• 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.

अधिगम पथ

• Computer science and formal methods

आगे पढ़ने के लिए

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