C

1

0

1

0

D

0

0

1

1

4. Явное задание графа как алгебраической системы:

<{a,b,c,d },{u,v,w,x }; {(u,a ),(u,b ),(v,b ),(v,c ),(w,c ),(w,a ),(x,c ), (x,d )}>.

Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d }; {(a,b ), (b,a ),(b,c ),(c,b ),(a,c ),(c,a ),(c,d ),(d,c )}>. В таком представлении ребру соответствуют две пары вершин (v ₁ ,v ₂ ) и (v ₂ ,v ₁ ), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b },{b,c },{a,c },{c,d }} и граф мы будем записывать как пару (V,E ), где V – множество вершин, а E – множество рёбер.

5. Наконец, граф можно задать посредством списков .

Например:

вариант 1 : списком пар вершин, соединенных ребрами (или дугами);

вариант 2 : списком списков для каждой вершины множества смежных с ней вершин.

2. Задачи на графах.

2.1. Описание различных задач на графах.

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

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

Далее перечислим некоторые типовые задачи теории графов и их приложения:

- Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

- Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью