. Нелинейное программирование. Все виды Н. П. Задачи. Функции и цели. Область применения - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Область определения – все значения переменной x. Область определения 1 19.41kb.
План: Система ценообразования Задачи, цели и функции ценообразования... 1 145.58kb.
Предмет, цели, задачи, виды деятельности, типы и виды реализуемых... 2 731.97kb.
П. Барсово Владимирская область 2012г Цели: формировать у учащихся... 1 94.03kb.
1. Цели и задачи проекта 1 213.88kb.
Многоугольники. Виды многоугольников 1 90.08kb.
Практическая работа: Используя предложенную форму, составить варианты... 1 19.19kb.
Задача №1. Линейные вычислительные процессы 1 38.17kb.
Задача Продифференцировать данные функции в 1 14.09kb.
Контрольная работа по теме «Алгоритмизация и программирование» 1 15.09kb.
Урока: Горные породы и минералы, определение и их назначение. 1 64.83kb.
Владыкина Елена Николаевна Тема урока : «Местоимение» (4 класс) 1 94.16kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

. Нелинейное программирование. Все виды Н. П. Задачи. Функции и цели. Область применения - страница №1/1



Содержание
.Нелинейное программирование. Все виды Н.П. Задачи. Функции и цели. Область применения……………………………………………………………..3
.Исследование операций. Ограничение, общие задачи, алгоритм решения…………………………………………………………………………...8
.Теория «Графов» Область применения. Задачи. Алгоритм решения……19
Список используемой литературы……………………………………………..

.Нелинейное программирование

1.Формулировка задачи и предварительное обсуждение

2.Критерии оптимальности в задачах с ограничениями

Нелинейное программирование подразделяется следующим образом: Выпуклое программирование – когда выпукла целевая функция и выпукло множество, на котором решается экстремальная задача. Квадратичное программирование – когда целевая функция квадратична, а ограничения – линейные равенства и неравенства. Многоэкстремальные задачи. Здесь обычно выделяют специализированные классы задач, часто встречающихся в приложениях, например, задача о минимизации на выпуклом множестве вогнутых функций.

Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.

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

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведённых товаров.

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

Но в целом задачи нелинейного программирования относятся к трудным вычислительным задачам. При их решении часто приходится прибегать к приближенным методам оптимизации. Мощным средством для решения задач нелинейного программирования являются численные методы. Они позволяют найти решение задачи с заданной степенью точности.


Общая формулировка нелинейных задач:
Найти переменные х1 , х2 , …, хn , удовлетворяющие системе уравнений Ψ ( х1 , х2 , …, хn ) = bi , i = 1, 2, …, m (2.24) и обращающие в максимум ( минимум ) целевую функцию Z = f ( х1 , х2 , …, хn ) (2.25)Примером типичной и простой нелинейной задачи является следующая:

Данное предприятие для производства какого-то продукта расходует два средства в количестве х1 и х2 соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п., а величины х1 и х2 – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства Z = f ( х1 , х2 ). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х1 и х2) и от цен этих факторов (c1 и c2). Совокупные издержки выражаются формулой b = c1 х1 + c2 х2. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z. Математическая модель этой задачи имеет вид: определить такие переменные х1 и х2, удовлетворяющие условиям c1 х1 + c2 х2 = b (2.26)

х1 ≥ 0, х2 ≥ 0, (2.27) при которых функция Z = f (х1, х2 ) (2.28) достигает максимума. Как правило, функция (2.28) может иметь произвольный нелинейный вид.

Использую классические методы оптимизации, следует четко представлять себе различие между локальным экстремумом функции, глобальным экстремумом и условным экстремумом. Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n ≥ 2). Будем полагать, что функция Z = f ( х1 , х2 , …, хn ) = f (X) дважды дифференцируема в точке Х* = (х1 *, х2 *, …, хn* ), (Х* € D(f)) и в некоторой ее окрестности. Если для всех точек Х этой окрестности f (X*) ≥ f (X) или f (X*) ≤ f (X), то говорят, что функция f (X) имеет экстремум в X* (соответственно максимум или минимум). Точка X* , в которой все частные производные функции Z = f (Х) равны 0, называется стационарной точкой.

Необходимое условие экстремума.

Если в точке X* функция Z = f (Х) имеет экстремум, то частные производные функции в этой точке равны 0:

f 'x1 (X*) = 0, i = 1, 2, ..., n.

Следовательно, точки экстремума функции Z = f (Х) удовлетворяют системе уравнений: (2.29) Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциала второго порядка обозначается d2f (х1 , х2 , …, хn ) f 'x1 (X) найти частную производную по переменной хj , то получим частную производную второго порядка по переменным хi , хj , которая обозначается f ''xi, xj (X). В этом случае

Достаточные условия экстремума.

Двух переменных:

если Δ > 0 и а11 < 0 (а22 < 0), то в точке Х 0 функция имеет максимум:

если Δ > 0 и а11 > 0 (а22 > 0),то в точке Х 0 – минимум (в этих случаях Х 0 = Х*);

если Δ < 0, то экстремума нет;

если Δ = 0, то вопрос об экстремуме остается открытым.

1.Формулировка задачи и предварительное обсуждение.
Задачи оптимизации (экстремальные задачи)


На минимум:

(1)

при ограничениях

(2)

(3)


На максимум:

(4)

при ограничениях

(5)

(6)

называются задачами нелинейного программирования (сокращенно задачами НЛП), если среди функций f,g1...gm,h1...,hk имеется хотя бы одна нелинейная функция. Записи (1)-(3) и (4)-(5) являются стандартными постановками задач минимума и максимума (обратите внимание на знаки неравенств в (2) и (5)).

Задачи НЛП, как и любые другие задачи оптимизации, являются математическими моделями некоторых практических задач принятия решения (примеры можно найти в книгах [1,8,12]).

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

В задаче (1)-(3) - целевая функция. допустимое множество (множество допустимых точек).

Решить задачу (1)-(3) это значит:

а) либо найти точку минимума (оптимальное решение)

б) либо убедиться, что задача (1)-(3) не имеет оптимального решения (функция f не ограничена снизу на X или X=).

Если минимум функции f не достигается на множестве X (разрывность f, открытость или неограниченность X), то вместо задачи (1)-(3) ставится обобщенная задача: f(х)  inf при ограничениях (2)-(3) решение которой в виде минимизирующей последовательности почти всегда существует.

Как и в любой теории принятия решения, перед теорией нелинейной оптимизации стоят следующие три основные проблемы:

1) проблема существования оптимального решения;

2) проблема установления необходимых и достаточных признаков оптимальности (характерных свойств, присущих точкам минимума и максимума);

3) разработка способов вычисления оптимальных решений (методов решения задач НЛП).

, , сохранив тем самым типовую формулировку задачи.


2. Критерии оптимальности в задачах с ограничениями.
Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмотрения задач оптимизации, которые содержат только ограничения в виде равенств.

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


Названием “методы нелинейного программирования” объединяется большая группа численных методов, многие из которых приспособлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.

.Исследование операций

Решение задач исследования операций


Решение задачи 1
Для составления математической модели задачи введём переменные:

– количество горючего, доставляемое со склада A на бензоколонку 1

– количество горючего, доставляемое со склада A на бензоколонку 2

x3a – количество горючего, доставляемое со склада A на бензоколонку 3

x1b – количество горючего, доставляемое со склада B на бензоколонку 1

x2b – количество горючего, доставляемое со склада B на бензоколонку 2

x3b – количество горючего, доставляемое со склада B на бензоколонку 3

x1c – количество горючего, доставляемое со склада C на бензоколонку 1

x2c – количество горючего, доставляемое со склада C на бензоколонку 2

x3c – количество горючего, доставляемое со склада C на бензоколонку 3

На складах A, B, C находится 90, 60, 90 тонн горючего соответственно, следовательно, можно записать:

На каждую заправку нужно оправить одинаковое количество горючего, равное (90+60+90)/3:



В соответствии со стоимостями перевозок запишем целевую функцию, которую необходимо минимизировать:



Имеем классическую транспортную задачу с числом базисных переменных, равным n+m–1 , где m–число пунктов отправления, а n – пунктов назначения. В решаемой задаче число базисных переменных равно 3+3-1=5.

Число свободных переменных соответственно 9-4=4.

Примем переменные x1a, x1b, x2a, x2с, x3с в качестве базисных, а переменные x1c, x2b, x3а, x3b в качестве свободных (данный выбор позволяет легко выразить базисные переменные через свободные).

Далее в соответствии с алгоритмом Симплекс метода необходимо выразить базисные переменные через свободные:

Следующий шаг решения – представление целевой функции через свободные переменные:



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

Составим Симплекс таблицу:






bi

x3a

x2b

x3b

x1c

L

630

-10


-3

1


-1

0


-4

4


1

-1


x1a

20

-10


0

1


-1

0


-1

1


1

-1


x1b

60

0


0

0


1

0


1

0


0

0


x2a

70

10


1

-1


1

0


1

-1


-1

1


x2c

10

10


-1

-1


0

0


-1

-1


1

1


x3c

80

0


1

0


0

0


1

0


0

0

Выбор в качестве разрешающей строки х2с обусловлен тем, что именно в этой строке отношение свободного члена к переменной х1с минимально. Выполним необходимые преобразования над элементами Симплекс таблицы:





bi

x3a

x2b

x3b

x2c

L

620

-2

-1

0

-1

x1a

10

1

-1

0

-1

x1b

60

0

1

1

0

x2a

80

0

1

0

1

x1c

10

-1

0

-1

1

x3c

80

1

0

1

0

Все коэффициенты при свободных переменных неположительные, следовательно, найденное решение является оптимальным. Запишем его:

x1a=10; x1b=60; x1c=10;

x2a=80; x2b=0; x2c=0;

x3a=0; x3b=0; x3c=80;

L=620;


Для проверки правильности вычислений можно составить транспортную таблицу:




A

B

C




1

10

60

10

80

2

80

0

0

80

3

0

0

80

80




90

60

90



После анализа таблицы можно сделать вывод, что вычислительных ошибок при расчетах сделано не было.

Ответ:

x1a=10 x1b=60 x1c=10

x2a=80 x2b=0 x2c=0

x3a=0 x3b=0 x3c=80

L=620
Решение задачи 2
Составим систему ограничений исходя из условия задачи

Целевая функция задачи имеет вид:



Пусть переменные x1 и x2 - свободные, а переменные x3, x4 и x5 – базисные.

Далее необходимо представить систему ограничений в стандартном виде. Для этого проведем ряд преобразований:

Подставим выражения для x3 и x4 в третье уравнение системы ограничений:



Упростим полученное выражение и выразим x5:



Теперь можно представить систему ограничений в стандартном виде:



Необходимо также выразить целевую функцию через свободные переменные:



Теперь можно заполнить Симплекс-таблицу







bi

x1

x2

L

1

-1

-3

x3

2

-1

2

x4

2

1

1

x5

1

1

-1

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

Далее нужно выбрать разрешающий элемент. В качестве разрешающего столбца целесообразно принять столбец x1, так как коэффициент при x1 в целевой функции меньше коэффициента при x2. Разрешающей строкой будет строка x5, так как отношение свободного члена этой строки к коэффициенту при x1 минимально. Отметим найденный разрешающий элемент в таблице, а также заполним необходимые клетки:





bi

x1

x2

L

1

1


-1

1


-3

-1


x3

2

1


-1

1


2

-1


x4

2

-1


1

-1


1

1


x5

1

1


1

1


-1

-1

Перерисуем таблицу с учётом замены x2 на x3:





bi

x5

x2

L

2

1

-4

x3

3

1

1

x4

1

-1

2

x1

1

1

-1

Коэффициент при х2 в целевой функции отрицателен, значит необходимо произвести ещё одну замену. В качестве разрешающей строки примем x3. Таким образом, разрешающим будет элемент, стоящий на пересечении строки x3 и столбца x2.







bi

x5

x2

L

2

12


1

4


-4

4


x3

3

3


1

1


1

1


x4

1

-6


-1

-2


2

-2


x1

1

3


1

1


-1

1

В итоге получим:





bi

x5

x3

L

14

5

4

x2

3

1

1

x4

-5

-1

0

x1

4

2

1

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

Ответ: x1=4;x2=3;x3=0;x4=-5;x5=0;L=14.


Решение задачи 3
Условие задачи задано в виде транспортной таблицы:


ПН

ПО


B1

B2

B3

запасы

A1

50

15

10

300

A2

21

30

20

100

A3

18

40

25

200

A4

23

22

12

800

A5

25

32

45

200

заявки

500

300

800



Применим к задаче метод «Северо-Западного угла». Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок:




ПН

ПО


B1

B2

B3

запасы

A1

300







300

A2

100







100

A3

100

100




200

A4




200

600

800

A5







200

200

заявки

500

300

800



В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна.




ПН

ПО


B1

B2

B3

запасы

A1

50

300


15

10

300

A2

21

100


30

20

100

A3

18

100


40

100


25

200

A4

23


22

200


12

600


800

A5

25


32

45

200


200

заявки

500

300

800



В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл γ1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки:

ΔL1=-5*100=-500

Транспортная таблица примет следующий вид:




ПН

ПО


B1

B2

B3

запасы

A1

50

300


15

10

300

A2

21

100


30

20

100

A3

18

100


40


25

100


200

A4

23


22

300


12

500


800

A5

25


32

45

200


200

заявки

500

300

800



γ2=12+32-45-22=-23 k2=200 ΔL2=-23*200=-4600




ПН

ПО


B1

B2

B3

запасы

A1

50

300


15

10

300

A2

21

100


30

20

100

A3

18

100


40


25

100


200

A4

23


22

100


12

700


800

A5

25


32

200


45


200

заявки

500

300

800



γ3=10+18-50-25=-47 k3=100 ΔL3=-47*100=-4700




ПН

ПО


B1

B2

B3

запасы

A1

50

200


15

10

100


300

A2

21

100


30

20

100

A3

18

200


40


25


200

A4

23


22

100


12

700


800

A5

25


32

200


45


200

заявки

500

300

800




γ4=10+23-12-50=-29 k4=200 ΔL4=-29*200=-6800


ПН

ПО


B1

B2

B3

запасы

A1

50


15

10

300


300

A2

21

100


30

20

100

A3

18

200


40


25


200

A4

23

200


22

100


12

500


800

A5

25


32

200


45


200

заявки

500

300

800



Отрицательных циклов в транспортной таблице больше нет. Следовательно, можно предположить, что найденное решение является оптимальным. Для проверки применим метод потенциалов.

Составим систему:

Положим β2=0, тогда α4=-22

β1=1, α2=-20

β3=-10, α2=-22

α1=-20, α5=-32

Все коэффициенты α отрицательны, значит, найденный план перевозок является оптимальным.

Ответ:

x21=100;x31=200;x41=200;x42=100;x52=200;x13=300; x43=500.




Решение задачи 4
Составим математическую модель поставленной задачи.

Найти минимум функции f(x1,x2)



При ограничениях

Заменив знак функции f(x1,x2) на противоположный, перейдем к поиску максимума функции:

Теперь задача приведена к стандартному виду задачи квадратичного программирования. Приступим к решению.

1) Определим стационарную точку

Решив систему, получим:

x1=10

x2=7


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

2) Составим функцию Лагранжа:



Применив к функции Лагранжа теорему Куна-Таккера, будем иметь систему:



3) Преобразуем полученную систему:



Из уравнения 3 системы следует, что x2=6-x1:



Для обращения неравенств системы в равенства введём V1, V2, W и преобразуем систему:



4) Запишем условия дополняющей нежесткости:



5) Введем в систему уравнений искусственные переменные z1,z2:



Поставим задачу максимизации функции .

Для решения этой задачи воспользуемся Симплекс-методом. Примем переменные z1 и z2 в качестве базисных:



Составим Симплекс таблицу:







bi

x1

U1

U2

V1

V2

φ

-17M

0


-5M

0


0

0


M

0


M

0


-M

0


z1

9

8


2

3


-1

1


2

-3


-1

0


0

1


z2

8

8


3

3


1

1


-3

-3


0

0


1

1


W

0

0


-1

0


0

0


0

0


0

0


0

0








bi

x1

z2

U2

V1

V2

φ

-17M

17M


-5M

M


0

M


M

-M


M

-M


-M

M


z1

17

17/5


5

1/5


1

1/5


-1

-1/5


-1

-1/5


1

1/5


U1

8

-51/5


3

-3/5


1

-3/5


-3

3/5


0

3/5


1

-3/5


W

0

17/5


-1

1/5


0

1/5


0

-1/5


0

-1/5


0

1/5








bi

z1

z2

U2

V1

V2

φ

0

M

M

0

0

0

x1

17/5

1/5

1/5

-1/5

-1/5

1/5

U1

-11/5

-3/5

-2/5

1/2

3/5

-2/5

W

17/5

1/5

1/5

-1/5

-1/5

1/5

В итоге получим

x1=17/5 x2=6-x1=13/5

Как видно, координаты стационарной точки сильно отличаются от координат, полученных в качестве ответа. Это можно объяснить тем, что стационарная точка не удовлетворяет условиям ограничений.

Условия дополняющей нежесткости

выполняются.

Следовательно, найденное решение является оптимальным.

Найдем значения целевой функции:

=- 51/5 - 52/5 + 289/50 – 221/25 + 169/25 = -16.9

Ответ:


x1 = 17/5 ;x2 = 13/5 ;f(x1,x2) = -16.9.

 Теория графов

Графы и их применение

1. Основные понятия теории графов

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

Рис. 1 Рис. 2


Но для огромного (и все возрастающего) числа математиков слово «граф» означает нечто совсем иное.

Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако, эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен, главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это, благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развития формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач – проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

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

ГРАФЫ И ИХ ПРИМЕНЕНИЕ
1. Основные понятия теории графов
Пусть дано множество V = {v1, v2,…,vn} и пусть на множестве V определено семейство U = {u1, u2, …, un} пар элементов Uk = {vi, vj}, (k=1, m) произвольной кратности и упорядочения. Пара {V, U} называется графом. Граф, как правило, обозначают прописными латинскими буквами, например G, H. Принято также писать G (V, U) для того, чтобы определить некоторый конкретный граф G.

Элементы v1, v2,…, vn называют вершинами графа, а пары Uк = {vi, vj},


(к = 1, m) – ребрами.
Определению графа можно дать такую интерпретацию. Пусть имеем описание графа:

G (V, U) = {{v1, v2,…, v6}, {{v1, v3}, , {v3, v4}, , {v3, v3}}}.


Это описание можно отобразить графически, как показано на рис.3. На этом рисунке некоторые ребра отмечены стрелкой, а соответствующие им пары вершин в описании графа выделены угловыми скобками. Это связано с тем, что для некоторого произвольного ребра можно принимать или не принимать во внимание порядок расположения его концов.

Если этот порядок не существенен, то ребро называется неориентированным, в противном случае ребро называется ориентированным. Ориентированные ребра называются также дугами. V1

V5

V2

VH

V3

V6

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

Ребра {v1, v3}, {v3, v4} неориентированы. Для любого неориентированного ребра полагают, что {vi, vj} = {vj, vi}. Ребро {vi, vi} называется петлей. На рис.3 имеем петлю {v3, v3}. Петли обычно неориентированы.

Граф, у которого все ребра неориентированы, называется неориентированным.

Граф, у которого все ребра ориентированы, называется ориентированным или орграфом.

Иногда удобно преобразовывать неориентированный граф в ориентированный – заменой каждого неориентированного ребра парой ориентированных ребер с противоположной ориентацией.

На рис.3 приведен смешанный граф, т.е. содержащий как ориентированные, так и неориентированные ребра и петлю.

Некоторые вершину графа G могут не войти в список пар. Такие вершины называются изолированными. В рассмотренном примере это вершина v6. Граф, у которого все вершины изолированы, называется нуль-графом. Множество ребер такого графа пусто.

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

Как в случае ориентированного графа, так и в случае неориентированного, говорят, что ребро инцидентно паре определяющих его вершин.

Одной и той же паре вершин можно поставить в соответствии множество инцидентных ребер. Такие ребра называются кранными. Так, на рис.4 представлены различные пары вершин (vi, vj), инцидентных трем различным ребрам u1, u2, u3. Одно из них направлено, а два – нет.
V1

V4

V3

V2

Рис. 4
Граф называется плоским, если он может быть изображен на плоскости так, что все пересечения ребер есть его вершины. Так, граф приведенный на рис.3, плоским не является, а на рис.4 – плоский.

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

Граф Н называется частью графа G или частичным графом Н С G, если множество его вершин V (G) графа G и все ребра U являются ребрами G. Частным, но важным типом частичных графов являются подграфы.

Пусть А – подмножество множества вершин V графа G. Подграф G (A) графа G есть такая часть графа, множеством вершин которого является А, а ребрами – все ребра из G, оба конца которых лежат в А.

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

Например, граф G на рис.5 неполный. А проведенные недостающие ребра составляют граф дополнение G рис.6.


G:

Рис. 5 Рис. 6


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

Обозначать степени вершин v1, v2, v3 будем так: δ (v1), δ (v2), δ (v3) и т.п.

У графа на рис.7 δ (v1) = 1; δ (v2) = 2. У графа на рис. 8 степени всех вершин равны нулю.
V1

V3

V4

V2

V1

V3

V4

V2

Рис. 7 Рис. 8
При решении задач и доказательстве теорем использовались разные способы задания графов. На рисунках граф изображался с помощью точек (крутков, квадратиков) и отрезков, соединяющих пары точек. Можно граф представить специальной таблицей. Пользуются еще матричным представлением графа. Выбирают то представление или способ, который удобнее и нагляднее при рассмотрении конкретного вопроса.

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

Пусть имеем граф G (V, U). Его матрицей смежности называется квадратная матрица (аi, j) порядка n2, где n – число вершин, а аi, j – число ребер, инцидентных вершинам vi и vj. Если граф не имеет кратных ребер, то аi, j = 1, когда vi и vj смежные, и аi, j = 0, когда vi и vj не смежные. Если граф не имеет петель, то все его диагональные элементы равны нулю.

Рассмотрим примеры. На рис. 9 изображены три неориентированных графа. В первом случае (рис.9а) имеем граф без петель и без кратных ребер. Во втором случае (рис.9б) имеем кратные ребра. В третьем случае (рис.9в) в вершинах v1 и v4 имеются петли.

V3

V2

V4

V1

V3

V2

V4

V1

V3

V2

V4

V1

а б в

Рис. 9


Соответствующие этим трем случаям матрицы смежности представлены ниже:
а) б) в)
Для неориентированного графа матрица смежности является симметрической. Для ориентированного графа матрица смежности симметрической, вообще говоря, не является.

Матрицей инциденций неориентированного графа, называется матрица (bi,j) размера n · m, где n – число вершин, а m – число ребер, построенная по правилу



Соответствующие рис.9б матрицы инциденций представлены ниже.


Примечание: для графа на рис. 9б приняты следующие обозначения ребер: Х1 = (v1, v2)1, Х2 = (v1, v2)2, Х3 = (v1, v4)1, Х4 = (v1, v4)2, Х5 = (v1, v4)3, Х6 = (v2, v4), Х7 = (v3, v2).

Матрица инциденций неориентированного графа обладает следующими очевидными свойствами:

1) в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра;

2) если в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных – по две.

Матрицей инциденций ориентированного графа называется матрица (bi, j) размера n · m, где n – число вершин, а m – число ребер, построенная по правилу

Рассмотрим, например, граф, изображенный на рис.10.
V4

V3

V2

V1

V5

V6

Рис. 10

Построенная в соответствии с описанным правилом матрица инциденций этого графа имеет вид



Примечание: для графа на рис.10 приняты следующие обозначения дуг: Х1 = (v1, v2), Х2 = (v1, v3), Х3 = (v3, v2), Х4 = (v3, v4), Х5 = (v5, v4), Х6 = (v5, v6), Х7 = (v6, v5).

Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра.

Задачи, возникающие на практике, приводят к разного вида операциям над матрицами. Рассмотрим некоторые из них.

Пусть система авиалиний между городами Х1, Х2, Х3 одной страны и городами У1 и У2 другой страны задается подмножеством пар: (Х1, У1), (Х1, У2), (Х2, У1), (Х2, У2), (Х3, У2), т.е. множеством ребер соответствующего графа. Система связи между этими же городами водным транспортом задается другим подмножеством пар: (Х1, У1), (Х2, У1), (Х2, У2), (Х3, У1). Кроме этого, для каждой пары городов (Хi, Уj). Известно число различных водных и авиамаршрутов. Эти числа можно проставить над ребрами на рисунке графа или зафиксировать с помощью двух матриц одинакового порядка:


У1 У2 У1 У2

Х1 4 1 Х1 2 0

А = Х2 2 6 В = Х2 1 3

Х3 0 4 Х3 2 0


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

Естественно, что для этого достаточно сложить соответствующие элементы матриц А и В. Ответ можно записать с помощью новой матрицы того же порядка:


У1 У2

Х1 6 1


С = Х2 3 9

Х3 2 4
В общем случае операцию сложения двух матриц можно записать так: если А = (аi,j) и В = (bi,j) – матрицы одного порядка, то матрица С = А + В = (Сi,j), где Сi,j = аi,j + bi,j.

Рассмотрим еще одну задачу. Пусть в каких-то трех странах выделены некоторые города, связанные с транспортом четырех видов: воздушным, железнодорожным, водным и автобусным. Схема транспортных связей между городами Х1 и Х2, принадлежащими первой стране, и городами У1, У2, У3, принадлежащими второй стране, зафиксирована матрицей А, где аi,j показывает на число видов транспорта, соединяющих города Хi и Уi. Аналогичная схема транспортных связей между городами У1, У2, У3, принадлежащими второй стране, и городами Z1, Z2, принадлежащим третьей стране, представлена матрицей В. Какие конкретно виды транспорта связывают пары городов, нас не интересует. Города первой и третьей стран непосредственных связей не имеют.

У1 У2 У3 Z1 Z2

А = Х1 4 0 2 У1 2 1

Х2 2 3 1 В = У2 0 3

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

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

Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С:
Z1 Z2

C = Х1 С11 С12

Х2 С21 С22
Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно
Z1 Z2

C = Х1 (а11в11 + а12в21 + а13в31 а11в12 + а12в22 + а13в32

Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32

Z1 Z2


C = Х1 14 4

Х2 7 11
Рассмотренная задача убеждает в целесообразности введения еще одной операции над матрицами. Эту операцию принято называть операцией умножения матриц.

Если С = АВ, то элементы матрицы С определяются следующей формулой:
сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj
Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В.

Следует обратить внимание на следующие два факта:

1) операция умножения матрицы А на матрицу В определена только в том случае, если число столбцов в матрице А равно числу строк в матрице В.

2) если матрица А имеет порядок (m x n), а матрица В – порядок (n x r), то матрица – произведение С = АВ имеет порядок (n x m).

Рассмотрим некоторые основные операции, производимые над графами.

Операцией добавления к графу G = вершины а образуется граф .

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

Пример:


5

3

4



2

1

3



4

2

1



3

4

2



1

3

4



2

1

3



4

1

3



2

1

4



2

1

G



G1

G2

G3

G4

G5

G6

Рис. 11
Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) – G2, удалением дуги (3, 2) – G3, удалением вершины 2 – G4, отождествлением вершин 1 и 4 – G5 , стягиванием дуги (2, 3) – G6.

Добавлением графа без петель G = называется граф = .


1

2

3



4

1

2



3

4

G



G

Рис. 12
Объединением G1 u G2 называется граф .

Если V1 ∩ V2 ≠ Ø, то пересечением G1 ∩ G2 называется граф .

Кольцевой суммой G1 + G2, называется граф

Соединением G1 + G2 называется .

Произведением G1 x G2 называется граф .

Композицией G1 [G2] называется граф , в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2.

1V3

1V2

1V4

V2

V2

V4

V5

V5

V4

V3

V1

V3

V2

G1

V1

V3

V2

G2

V1

V3

V2

G1G2

Vn

V2

V1

G1G2

V1

V3

V2

G1G2

Vn

V1

V2

G1

G2

V1

V3

G1 +G2

1

2



G1

G2

V1

V2

V3

2V3

2V2

2V4

G1 ∙ G2

1V3

1V2

1V4

2V3

2V2

2V4

G1 ∙ [G2]

Рис. 13
Рассмотрим специальный класс графов, имеющий важное практическое значение, представители которого именуются деревьями.

Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф называется лесом. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов.

Рис. 14 Рис. 15
Пример дерева показан на рис.14, здесь же показаны висячие вершины, на рисунке они выделены закрашенными кружками (вершина дерева, степень которой равна единице, называется висячей вершиной).

Пример леса показан на рис.15.

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

Теорема: дерево с n вершинами имеет n-1 ребро.

Для того, чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трех деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с n вершинами можно получить n деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить n-1 ребро из дерева Г. Итак, действительно, в дереве с n вершинами n-1 ребро.

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


ПИЩА

7

4



3

0

СТАРТ



2

1

5



6

Рис. 16


Ответ: 8 способами

Рис. 17
2. Расстояния в графах. Диаметр, радиус, центр графа


Пусть G = - связный неорграф, Vi, Vj – две его несовпадающие вершины.

Длина кратчайшего (Vi, Vj)-маршрута называется расстоянием между вершинами Vi и Vj и обозначается через ρ (Vi, Vj).

Положим ρ (Vi, Vj) = 0. Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:
1) ρ (Vi, Vj) ≥ 0;

2) ρ (Vi, Vj) = 0 ↔ Vi = Vj

3) ρ (Vi, Vj) = ρ (Vi, Vj) – симметричность

4) ρ (Vi, Vj) ≤ ρ (Vi, Vj) + ρ (Vj, Vк) – неравенство треугольника.


Если V = {V1, V2,…, Vn}, то матрица Р = (рi,j) = ρ (Vi, Vj), называется матрицей расстояний (где матрица Р симметрична).

Для фиксированной вершины V величина Е (v) = мах { ρ (Vi, Vj) | Vj є V} называется эксцентриситетом вершины V. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.

Если Р-матрица расстояний, то эксцентриситет Е (Vi) равен наибольшему из числе, стоящих в i-й строке.

Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d (G) : d (G) = vf[ {E(v) | v є V}. Вершина V называется периферийной, если Е (v) = d (G).

Рассмотрим пример. Найдем диаметр графа G, изображенный на рис.18. Матрица расстояний Р имеет вид:

Рис. 18
Отсюда Е (1) = 3, Е (2) = 2, Е (3) = 3, Е (4) = 2, Е (5) = 2 и, следовательно, d (G) = 3. Вершины 1 и 3 являются периферийными.

Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r (G) : r (G) = min {E (vi) | vi є V}.

Вершина V называется центральной, если Е (v) = r (G).

Множество всех центральных вершин графа называется его центром.

Рассмотрим соответствующий пример. Радиус графа, показанного на рис.18, равен 2, а его центром является множество {2, 4, 5}.

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

Дерево – одно из наиболее часто встречающихся в теории графов понятий (рис.19).

Ясно, что «особое место» в дереве занимают не только висячие вершины. Выделяются в этих деревьях и вершины, отмеченные двойным кружком. Такие вершины называют корневыми.

Корневую вершину нетрудно также выделить у деревьев на рисунках 20, 21, 22.

В первом случае корневой вершиной является единственная вершина графа А, во втором – вершина С, в третьем (такое дерево, все вершины которого, кроме одной, висячие, называют «звездой») – вершина А. Но какие вершины считать корневыми в графах, которые изображены на рисунках 23, 24 и 25?

Естественно считать, что все эти три дерева имеют по две корневые вершины. У дерева на рисунке 23 – это А и В, у дерева на рисунке 24 – это С и Д, у дерева на рисунке 25 – это А и В.

Расстоянием d (Vi, Vj) между вершинами Vi и Vj графа G называют длину кратчайшего пути, их соединяющего. (Если граф G-дерево, то путь соединяющий вершины Vi и Vj, единственный).

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

Наибольшее из таких чисел называют диаметром графа (в данном случае дерева), наименьшее – радиусом графа.

Вершины дерева, для которых максимальное из расстояний до других вершин равно радиусу, называются корневыми. Для дерева, изображенного на рисунке 26, диаметр равен 5, а радиус равен 3; корневые вершины – А и В.

Задача. Подсчитайте диаметр и радиус графа, изображенного на рисунке:

а) 18; б) 24; в) 25.

Английский математик А.Кэли в 1875 году опубликовал первую работу по применению теории графов в органической химии. При этом он использовал понятие «висячая вершина» дерева для подсчета числа изомеров предельных (не имеющих циклов) углеводородов.

Решим еще одну задачу по химии: «Насыщенным углеводородом называется соединение углерода С, имеющего валентность 4 и водорода Н, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n атомов углерода».

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

В построенном графе можно перейти по ребрам от любой вершины к любой другой, и в нем нет циклов. Такой граф называется деревом. Пусть молекула содержит n атомов углерода и m атомов водорода, тогда граф будет содержать n + m вершин. Далее, при решении задачи воспользуемся легко доказываемым соотношением: в дереве число ребер на единицу меньше числа вершин. Следовательно, в графе n + m – 1 ребер. Из вершин графа, обозначающих атомы углерода, выходит по 4 ребра, а из вершин, обозначающих атомы водорода, - одно. Используя простой факт, что сумма степеней вершин, т.е. сумма числа ребер, можно написать соотношение: 4n + m = 2 (n + m – 1). Отсюда получаем, что m = 2n + 2. Следовательно, формула насыщенного углеводорода, имеющего n атомов углерода: Сn H2n+n.

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

К числу предельных (не имеющих цикла) углеводородов относится, например пентан С5Н12. Его структурная формула изображена на рисунке 28. Этой формуле можно поставить во взаимно однозначное соответствие однокорневое дерево (рис. 29), показывающее взаимное расположение только атомов углерода в молекуле пентана. Но тем самым определяется однозначно и расположение атомов водорода в этой молекуле. На рисунке 30 представлена структурная формула молекулы одного из изопентанов, а на рисунке 31 соответствующее ей двукорневое дерево.

По тем или иным причинам почти все работы по теории графов таят в себе семена возможных практических применений или по крайней мере потенциально полезны.

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


ПРИЛОЖЕНИЕ ТЕОРИИ ГРАФОВ В РАЗЛИЧНЫХ

ОБЛАСТЯХ НАУКИ И ТЕХНИКИ.
Графы и информация
Двоичные деревья играют весьма важную роль в теории информации. Предположим, что определенное число сообщений требуется закодировать в виде конечных последовательностей различной длины, состоящих из нулей и единиц. Если вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя длина слов минимальна по сравнению с прочими распределениями вероятности. Задачу о построении такого оптимального кода позволяет решить алгоритм Хаффмана.

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



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

CnH2n+2

Все атомы углеводорода четырехвалентны, все атомы водорода одновалентны. Структурные формулы простейших углеводородов показаны на рисунке 6.1 (а – метан CH4, б – этан C2H6).

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

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


Графы и биология
Деревья играют большую роль в биологической теории ветвящихся процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся процессов – размножение бактерий. Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. Тогда для потомства одной бактерии мы получим двоичное дерево. Нас будет интересовать лишь один вопрос: в скольких случаях n-е поколение одной бактерии насчитывает ровно k потомков? Рекуррентное соотношение, обозначающее число необходимых случаев, известно в биологии под названием процесса Гальтона-Ватсона. Его можно рассматривать как частный случай многих общих формул.
Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

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


Список используемой литературы


1. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика: Учебное пособие. – Ростов н/Д: «Феникс», Харьков: «Торсинг», 2009. – 144 с.

2. Балк М.Б., Балк Г.Д. Математический факультатив – вчера, сегодня, завтра // Математика в школе. – 2007. - №3.

3. Березина Л.Ю. Графы и их применение – М., Просвещение, 1979.

4. Оре О. Теория графов. М., Наука, 1968.

5. Педагогика: Учеб. пособие для студентов пед.ин-тов. Под ред. Ю.К.Бабанского. М.: Просвещение, 1983.

6. Рогачев С.В. Граф на службе у географии // География в школе. – 2005. - №29 (91).

7. Судоплатов С.В., Овчинниова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск. Изд-во НГТУ, 2002.

8. Теория и методика обучения физике в школе: общие вопросы: Учеб. пособие для студ. высш.пед.учеб. заведений / С.Е.Каменецкий, Н.С.Пурышева, Н.Е.Вашеевская и др. Под ред. С.Е.Каменецкого, Н.С.Пурышевой. – М.: Издательский центр «Академия», 2009.



9. Энциклопедический словарь юного математика / Сост. А.П.Савин. – М.: Педагогика, 1985.