Darasa la 9–12Discrete MathematicsImepangwa
Graphs
Graphs as vertices and edges, degree and the handshake lemma, paths and connectivity, Euler circuits, trees and graph isomorphism.
math.discrete.graph-basics
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 11 (hadi chini kabisa)
Utajifunza
- 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.
Fasili
- 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.
Nadharia
- 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.
Mawazo potofu ya kawaida
- 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).
Inaelekea kwa
Ugunduzi wa hiari
- 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.
Njia za kujifunza
Usomaji zaidi
- J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)