Курсовая работа (т): Метрические характеристики графа

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

Необходимость. Пусть 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. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1.      d(u, v)≥0;

2.      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 все вершины являются центральными.

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

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

. Приложение теории графов в различных областях науки и техники

Информация.

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

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

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

Химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:

_nH_2n+2

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Молекула каждого предельного углеводорода представляет собой дерево. Если удалить все атомы водорода, то оставшиеся атомы углеводорода также будут образовывать дерево, каждая вершина которого имеет степень не выше 4. Следовательно, число возможных структур предельных углеводородов, т. е. число гомологов данного вещества, равно числу деревьев с вершинами степени не больше четырех.

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

Электротехника.

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

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

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

. Практическая часть

a)

Матрица смежности:

Матрица инцидентности:

Матрица расстояний:

Эксцентриситеты вершин:

e(x₂)=2

e(x₃)=2

e(x₄)=2

e(x₅)=1(x₆)=2

Передаточные числа вершин:

p(x₁)=6(x₂)=7(x₃)=6(x₄)=7(x₅)=5

p(x₆)=7

Диаметр графа равен 2, радиус - 1. Центр графа находится в вершине X₅. Медианы графа: x₂, x₄, x₆.

б)

Матрица смежности:

Матрица инцидентности:

Матрица расстояний:

Эксцентриситеты вершин:

e(x₁)=2(x₂)=2(x₃)=2(x₄)=1(x₅)=2

Передаточные числа вершин:

p(x₁)=5(x₂)=5(x₃)=5(x₄)=4(x₅)=5

Диаметр графа равен 2, радиус - 1. Центр графа находится в вершине X₄. Медианы графа: x₁, x₂, x₃, x₅.

. Листинг программы

uses crt;

var:array[1..100,1..100] of byte;,P:array[1..100] of byte;,i,j,m,d,r:byte;;('Enter quantity of tops the column and his matrix of a distance.');(n);;j:=1 to n doi:=1 to n do(A[i,j]);;j:=1 to n doi:=1 to n doi=nwriteln(A[i,j])write(A[i,j],' ');;;j:=1 to n do:=A[1,j];i:=1 to n dom<A[i,j]m:=A[i,j];;[j]:=m;;j:=1 to n doi:=1 to n do[j]:=P[j]+A[i,j];:=E[1];i:=1 to n dod<E[i]d:=E[i];:=E[1];i:=1 to n dor>E[i]r:=E[i];j:=1 to n do('e(x',j,')=',E[j]);;j:=1 to n do('p(x',j,')=',P[j]);;('d(G)=',d);('r(G)=',r);;('The centers the column:');i:=1 to n dor=E[i]write('x',i,' ');;('Medians the column:');:=P[1];i:=1 to n dom<P[i]m:=P[i];i:=1 to n dom=P[i]write('x',i,' ');;.