Теорема Веблена

У математиці теорема Веблена — твердження про те, що множину ребер скінченного графа можна подати у вигляді об'єднання простих циклів, яке не перетинаються, в тому і тільки в тому випадку, коли будь-яка вершина має парний степінь.

Довів Освальд Веблен.

Теорема тісно пов'язана з теоремою Ейлера про те, що скінченний граф має Ейлерів цикл (одиничний, не обов'язково простий, цикл, що покриває всі ребра графа) в тому і тільки в тому випадку, коли граф зв'язний і будь-яка вершина має парний степінь. Більш того, подання графа як об'єднання простих циклів можна отримати з Ейлерового циклу повторюваним поділом обходу на дрібніші цикли в разі наявності в циклі повторюваної вершини. Однак теорема Веблена справедлива і для незв'язних графів і її можна узагальнити на нескінченні графи, в яких кожна вершина має скінченний степінь.

Якщо в зліченному нескінченному графі G немає вершин з непарним степенем, його можна подати у вигляді об'єднання неперетинних (скінченних) простих циклів у тому і тільки в тому випадку, якщо будь-який скінченний підграф можна розширити (додаванням ребер і вершин із графа G) Ейлерового графа. Зокрема, будь-який зліченний нескінченний граф з єдиним кінцем, що не має вершин непарного степеня, можна подати як об'єднання циклів, що не перетинаються.

Див. також

• Базис циклів
• Покриття ребер циклами
• ^[en]

Примітки

1. Veblen, 1912.
2. Euler, 1736.
3. Sabidussi, 1964.

Посилання

• L. Euler. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Imperialis Petropolitanae. — 1736. — Т. 8. — С. 128—140.
• N. L. Biggs, E. K. Lloyd, R. J. Wilson . Graph Theory 1736—1936. — Oxford University Press, 1976.
• Gert Sabidussi . Infinite Euler graphs // . — 1964. — Т. 16. — С. 821—838. — DOI:10.4153/CJM-1964-078-x.
• Oswald Veblen . An Application of Modular Equations in Analysis Situs // Annals of Mathematics. — 1912. — Т. 14, вип. 1. — С. 86—94. — (Second Series).