Эйлеровость графов — различия между версиями
(Определения цикла и пути) |
(→Эйлеров путь, Эйлеров цикл) |
||
| Строка 1: | Строка 1: | ||
| − | ==Эйлеров путь | + | ==Эйлеров путь== |
| − | |||
Путь <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_(k-1)u_k -> u_k</math> в графе <math>G = (V, E)</math> <br/> | Путь <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_(k-1)u_k -> u_k</math> в графе <math>G = (V, E)</math> <br/> | ||
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/> | называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/> | ||
| − | + | ==Эйлеров цикл== | |
| + | |||
Цикл <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_k0-> u_0</math> в графе <math>G = (V, E)</math> <br/> | Цикл <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_k0-> u_0</math> в графе <math>G = (V, E)</math> <br/> | ||
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/> | называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/> | ||
| − | '''Эквивалентно:''' | + | '''Эквивалентно:''' |
Эйлеровым циклом является Эйлеров путь, являющийся циклом. | Эйлеровым циклом является Эйлеров путь, являющийся циклом. | ||
| + | |||
| + | ==Эйлеров граф== | ||
| + | ===Определение=== | ||
| + | Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл.<br/> | ||
| + | |||
| + | Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/> | ||
| + | |||
| + | ===Критерий Эйелеровости=== | ||
| + | ====Неориентированный граф==== | ||
| + | '''Теорема'''<br/> | ||
| + | Неориентированный связный граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.<br/> | ||
| + | |||
| + | ====Ориентированный граф==== | ||
Версия 03:59, 4 октября 2010
Содержание
Эйлеров путь
Путь в графе
называется Эйлеровым, если содержит все ребра , причем каждое - только один раз.
Эйлеров цикл
Цикл в графе
называется Эйлеровым, если содержит все ребра , причем каждое - только один раз.
Эквивалентно: Эйлеровым циклом является Эйлеров путь, являющийся циклом.
Эйлеров граф
Определение
Граф называется Эйлеровым, если содержит Эйлеров цикл.
Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым.
Критерий Эйелеровости
Неориентированный граф
Теорема
Неориентированный связный граф является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.
