Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
рис.6 (Эйлеровы графы)
Связные графы
Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.
Граф называется несвязным, если это условие не выполняется.
рис.7 
рис.8
На рисунке 7, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. (рис.8) Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом. Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8)
Несвязный граф состоит из нескольких «кусков». Эти «куски» называются компонентами связности графа. Каждая компонента связности является, конечно, связным графом. Отметим, что связный граф имеет одну компоненту связности.
ТЕОРЕМА. Граф является эйлеровым тогда и только тогда, когда он связен и имеет не более двух нечетных вершин.
Доказательство:
Рисуя граф каждую вершину, за исключением начальной и конечной, мы войдём столько же раз, сколько выйдем из неё. Поэтому степени всех вершин должны быть чётными, кроме двух, а значит, эйлеров граф имеет не более двух нечётных вершин.
Деревья
Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.
|
|
|
Циклом называется путь, в котором совпадают начало с концом.
Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией (рис.9а). В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.
Путем в графе от одной вершины к другой называется
Дата добавления: 2016-01-06; просмотров: 16; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!