пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

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

Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = <V, E>, где V -  множество вершин, E -рёбер.

Способы задания - матричный, аналитический, графический.

Если граф имеет цикл (необязательно простой), содержащий все рёбра графа  по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. 

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

Связность - имеет путь от вершины к вершине.
 

Цикломатическое число графа — минимальное число рёбер, которые надо удалить, чтобы граф стал ациклическим. Для связного графа существует соотношение: p_1(G) = p_0(G) + |E(G)| - |V(G)|, где p_1(G) — цикломатическое число, p_0 — число компонент связности графа, |E(G)| — число рёбер, а |V(G)| — число вершин.

Основное свойство цикломатического числа формулируется в виде теоремы:

Цикломатическое число мультиграфа равно максимальному числу независимых циклов.

09.06.2014; 00:59
хиты: 822
рейтинг:0
для добавления комментариев необходимо авторизироваться.
№ 1
я мучу этот
08 June 2014; 21:45

  Copyright © 2013-2024. All Rights Reserved. помощь