Зміст:
Введення. 2
1. Основні поняття теорії графів. 3
2. Матричні способи завдання графів. 4
3. Впорядкування елементів орграфа. 6
4. Постановка задачі про максимальний потік. Основні визначення. 8
5. Розріз на мережі. 11
6. Алгоритм рішення задачі про максимальний потік. 13
Висновок. 20
Список використаної літератури .. 21
Введення
В Останнім часом у різних областях знань широко застосовується теорія графів. З допомогою теорії графів добре описуються завдання економічної та планово-виробничої практики, як, наприклад, календарне та мережеве планування і управління, автоматизація управління виробництвом, раціоналізація схем перевезень і вантажопотоків, оптимальне розміщення виробництва т.п.
1. Основні поняття теорії графів
Основним об'єктом цієї теорії є граф. Наочно граф можна представити як деякий безліч точок площини або простору і безліч відрізків кривих або прямих ліній, з'єднують всі або деякі з цих точок. Формально граф G визначається завданням двох множин X і U і позначається G = (XU). Елементи xB 1B , xB 2B , ..., XB n B безлічі X називаються вершинами і зображуються точками. Елементами uB 1B , uB 2B , ..., UB m безлічі U є пари зв'язаних між собою елементів множини X і зображуються відрізками. Взаємне розташування, форма і довжини відрізків значення не мають. Якщо в парі вершин xB i B і B B xB j B вказано напрямок зв'язку, тобто вказано, яка вершина є першою, то відрізок UB 1 B називається дугою, а якщо орієнтація не вказана, - ребром.
Якщо в графі G всі елементи множини U зображуються дугами, то граф називається орієнтованим (орграф), якщо ребрами, - неорієнтованим.
На практиці використовуються графи, в яких множини X і U складаються з кінцевого числа елементів, тобто кінцеві графи. На малюнку розташовувати вершини графа можна довільно. Також довільно вибирається і форма з'єднують їх ліній. Тому один і той же граф (граф з однією і тією ж інформацією) може бути представлений у різних видах. Такі графи називаються ізоморфними.
Суміжними називають вершини графа, якщо вони різні і існує дуга (ребро), яка з'єднує ці вершини. Якщо дві дуги (ребра) мають загальну кінцеву вершину, то такі дуги (ребра) суміжні.
Послідовність дуг, в якій кінець кожної попередньої дуги збігається з початком наступної, називається шляхом в Орграф. Шлях, що проходить через усі вершини і при цьому тільки один раз, називається Гамільтона. Шлях, що включає всі дуги графа, і при цьому тільки по одному разу, називається ейлеровим. Повним шляхом називають будь-яку безперервну послідовність вершин і дуг, що йдуть від початкової вершини до кінцевої. Кінцевий шлях, у якого початкова вершина збігається з кінцевою, називається контуром.
Граф називається зв'язковим, якщо для будь-яких двох його вершин існує шлях, їх з'єднує, інакше граф називається незв'язних.
В економіці найчастіше використовуються два види графів: дерево і мережу.
Дерево являє собою зв'язний граф без циклів, що має вихідну вершину (корінь) і крайні вершини; шляху від вихідної вершини до крайніх вершин називаються гілками.
Якщо граф, взагалі кажучи, не зв'язний, не містить циклів, то кожна зв'язна його частина буде деревом. Такий граф називається лісом.
В додатку теорії графів до практичних завдань дугам (ребрам) графа зіставляють якісь числові характеристики. Наприклад, пропускна здатність транспортної магістралі, запас якого ресурсу, тривалість виконання якої-небудь роботи і т.д. Таким чином, дугам графа приписані певні ваги і граф G називається зваженим.
2. Матричні способи завдання графів
Граф може бути представлений як у вигляді малюнка, так і у вигляді матриці. Це буває необхідно при великому числі вершин і дуг (ребер), коли малюнок втрачає свою наочність. Матричне подання графів використовується при дослідженні його на ЕОМ.
Нехай є граф G, не містить петель, що має n вершин і m дуг (ребер). Графу G можна зіставити матрицю інціденцій графа G. Рядки m цієї матриці відповідають вершин, стовпці n - дугам (Ребрах) графа. Якщо граф орієнтований, то елементи aB ij B матриці інціденцій дорівнюють: (-1), якщо дуга u виходить з i-ї вершини; (+1), якщо дуга заходить в i-ю вершину. Якщо граф неорієнтовані, то елементами матриці будуть 1 і 0. На рис. 1.2 показані орграф і його матриця інціденцій, на рис. 1.3. - Неорієнтовані граф і матриця інціденцій.
uB 1 B
uB 2 B
uB 3 B
uB 4 B
uB 5 B
uB 6 B
uB 7 B
x B 1 B
-1
0
0
0
-1
-1
0
x B 2 B
1
-1
0
0
0
0
0
x B 3 B
0
0
0
1
1
0
-1
x B 4 B
0
1
1
0
0
0
0
x B 5 BBB
0
0
-1
0
0
1
1
Рис.1.2
uB 1 B
uB 2 B
uB 3 B
uB 4 B
|
 Український реферат переглянуто разів: |  Коментарів до українського реферату: 0 |
|
|
