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

Химия

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

CnH2n+2

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

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

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

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

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

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

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

ПРАКТИЧЕСКАЯ ЧАСТЬ

a)

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

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

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

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

e(x1) =2

e(x2) =2

e(x3) =2

e(x4) =2

e(x5) =1

e(x6) =2

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

p(x1) =6

p(x2) =7

p(x3) =6

p(x4) =7

p(x5) =5

p(x6) =7

Диаметр графа равен 2, радиус – 1. Центр графа находится в вершине X5. Медианы графа: x2, x4, x6.

б)

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

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

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

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

e(x1) =2

e(x2) =2

e(x3) =2

e(x4) =1

e(x5) =2

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

p(x1) =5

p(x2) =5

p(x3) =5

p(x4) =4

p(x5) =5

Диаметр графа равен 2, радиус – 1. Центр графа находится в вершине X4. Медианы графа: x1, x2, x3, x5.

ЛИСТИНГ ПРОГРАММЫ

uses crt;

var

A: array [1. .100,1. .100] of byte;

E,P: array [1. .100] of byte;

n, i,j,m,d,r: byte;

begin

clrscr;

writeln('Enter quantity of tops the column and his matrix of a distance. ');

readln(n);

writeln;

for j: =1 to n do

for i: =1 to n do

readln(A [i,j]);

clrscr;

for j: =1 to n do

for i: =1 to n do

if i=n

then writeln(A [i,j])

else write(A [i,j],' ');

writeln;

writeln;

for j: =1 to n do

begin

m: =A [1,j] ;

for i: =1 to n do

begin

if m<A [i,j]

then m: =A [i,j] ;

end;

E [j]: =m;

end;

for j: =1 to n do

for i: =1 to n do

P [j]: =P [j] +A [i,j] ;

d: =E [1] ;

for i: =1 to n do

if d<E [i]

then d: =E [i] ;

r: =E [1] ;

for i: =1 to n do

if r>E [i]

then r: =E [i] ;

for j: =1 to n do

writeln('e(x',j,') =',E [j]);

writeln;

for j: =1 to n do

writeln('p(x',j,') =',P [j]);

writeln;

writeln('d(G) =',d);

writeln('r(G) =',r);

writeln;

writeln('The centers the column: ');

for i: =1 to n do

if r=E [i]

then write('x', i,' ');

writeln;

writeln('Medians the column: ');

m: =P [1] ;

for i: =1 to n do

if m<P [i]

then m: =P [i] ;

for i: =1 to n do

if m=P [i]

then write('x', i,' ');

readkey;

end.

 Скачать реферат