Метрические характеристики графа

4) Для любых трех вершин u, w, v из существования (u, w) - цепи их и (w, v) - цепи, следует существование (u, v) - цепи. Причем может не существовать (u, v) - цепи, содержащей вершину w.

5) Объединение двух несовпадающих простых (u, v) - цепей содержит простой цикл.6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл. >Если два графа изоморфны:

1) то они одного порядка;

2) у них одинаковое количество ребер;

3) для произвольного i,0≤i≤n–1, (n – порядок графов) количество вершин степени i, у обоих графов одинаковое;

4) у них совпадают обхваты;

5) у них одинаковое количество простых циклов минимальной длины (по количеству ребер).

Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v) - маршрут.

Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же множестве.

Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "максимальный" означает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности.

Для ориентированного графа вводится понятие ориентированного маршр-та – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой ситуации служить путь (ориентированная цепь). Аналогом цикла служит контур (ориентированный цикл).

Орграф называется сильносвязным, если любые две его вершины достижимы друг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется сла-босвязным, если любые две вершины его основания соединены маршрутом. Орг-раф называется несвязным, если его основание несвязный псевдограф.

Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть остовной циклический маршрут.

Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1, ., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1, ., v), T2=(v, z1, ., v0). Но тогда циклический маршрут T’=(v0, x1, v1, ., xn, v0, y1, ., v, z1, ., v0) содержит большее число вершин, чем T, что противоречит выбору маршру-та T. Следовательно, T – остовной маршрут.

Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x, ., v, y, ., u, z, ., v0) – циклический маршрут. Тогда u достижима из v спомо-щью маршрута (v, y, ., u) – части маршрута T,– а v из u – с помощью маршрута (u, z, ., v0, x, ., v).3

Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.

Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.

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

МЕТРИЧЕСКИЕ ХАРАКТЕРИСТИКИ ГРАФА

Пусть G– связный граф, а uи v– две его несовпадающие вершины. Длина кратчайшего (u, v) - маршрута называется расстоянием между вершинами uи vи обозначается d(u, v). Положим d(u, u) =0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

d(u, v) ≥0;

d(u, v) =0 тогда и только тогда, когда u=v;

d(u, v) =d(v, u);

d(u, v) + d(v, w) =d(u, w) (неравенство треугольника).

Для фиксированной вершины u величина e(u) =max d (uv) называется эксцентриситетом вершины u. Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G). Тем самым

dG =max e(u)

Вершина v называется периферийной, если e(v) =d(G). Простая цепь длины d(G), расстояние между концами которой равно d(G), называется диаметральной цепью.

Минимальный из эксцентриситетов вершин связного графа называется его радиусом и обозначается через r(G).

Очевидно, что радиус графа не больше его диаметра.

Вершина v называется центральной, если e(v) =r(G). Множество всех центральных вершин графа называется его центром. Граф может иметь единственную центральную вершину или несколько центральных вершин. Наконец, центр графа может совпадать с множеством всех вершин. Например, центр простой цепи Pn при четном числе вершин n состоит ровно из двух вершин, а при нечетном – из одной; для цикла же Cn все вершины являются центральными.

Задача нахождения центральных вершин графа постоянно возникает в практической деятельности людей. Пусть, например, граф представляет сеть дорог, т.е. вершины его соответствуют отдельным населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, магазины. В подобных ситуациях критерий оптимальности часто заключается в оптимизации «наихудшего» случая, т.е. в минимизации расстояния от места обслуживания до наиболее удаленного пункта. Следовательно, местами размещения должны быть центральные вершины графа.

Реальные задачи (их называют минимаксными задачами размещения) отличаются от идеальной тем, что приходится ещё учитывать другие обстоятельства – фактические расстояния между отдельными пунктами, стоимость, время проезда и прочее. Для того чтобы учесть это, используют взвешенные графы.

ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ ОБЛАСТЯХ НАУКИ И ТЕХНИКИ.

Информация.

Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который можно либо "да", либо "нет". Утвердительному и отрицательному ответу соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда удается установить то, что требовалось.

Таким образом, если кому-то понадобится взять интервью у различных людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий вопрос, то план такого интервью можно представить в виде двоичного дерева.

Страница:  1  2  3  4 


Другие рефераты на тему «Математика»:

Поиск рефератов

Последние рефераты раздела

Copyright © 2010-2024 - www.refsru.com - рефераты, курсовые и дипломные работы