пользователей: 21244
предметов: 10456
вопросов: 177505
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Элементы теории графов: деревья, теорема Келли; плоские и планарные графы, теорема Эйлера, примеры неплоских графов.

Граф является деревом, если он удовлетворяет следующей теореме.

Теорема. Для графа G= <X,U> следующие утверждения эквивалентны:

1)  G - дерево;

2) любые две вершины в графе G соединены единственной простой цепью;

3) граф G связен и имеет  |X| - 1   ребер;

4) граф G не содержит циклов и имеет  |X| - 1   ребер;

5) граф G не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению одного цикла;

6) граф G связен, но утрачивает это свойство после удаления любого ребра.

Теорема Кэли о числе деревьев — названное в честь А. Кэли явное выражение в теории графов для числа деревьев с данным числом пронумерованных вершин. А именно, оказывается, что на n вершинах, пронумерованных числами от 1 до n, существует ровно n^{n-2} различных деревьев.

 

 Граф clip_image002.gif называется планарным, если хотя бы одна из его геометрических интерпретаций такова, что ребра графа пересекаются только в его вершинах. Например, граф:

clip_image004.jpg

Пусть clip_image011.gif - плоский граф. Это означает, что имеется определенное изображение его на плоскости, в котором ребра пересекаются только в вершинах. Каждый простой цикл такого графа ограничивает две части плоскости: одна - внутренняя (ограниченная), другая - внешняя (неограниченная):

clip_image012.gif

Теорема (Л. Эйлер, 1736 г.)

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.

image138.gif

На 4.11 плоский граф, на 4.12 неплоский.


10.06.2014; 00:05
хиты: 660
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь