Page 77 - 4496

одержуємо (одну з можливих) найкращих реберних
розфарбувань графів.
Відзначимо, що реберне розфарбування часто
застосовується при конструюванні різних пристроїв, де
проведення, що з'єднуються в одній вершині, повинні (для
зручності) мати різні кольори.

3.13 Мережі, потоки в мережах. Теорема Форда -
Фалкерсона

Мережею називається зв'язаний граф (звичайно, не
орграф і не мультиграф), у якому задані “пропускні здатності”
ребер, тобто числа qij. Ці числа більші або рівні нулю,
причому qij = 0 тоді й тільки тоді, коли немає ребра, що
з'єднує вершини i й j. Таким чином, можна вважати, що
пропускні здатності ребер задані для будь-якої пари вершин.
У дискретній математиці пропускні здатності ребер, як і всі
виникаючі константи, вважаються цілими числами (або
раціональними, тому що раціональні числа відрізняються від
цілих тільки одиницями вимірювання). Помітимо, що мережі
мають величезні додатки, зокрема, “мережі планування”
(мається на увазі планування виробництва деяких нових,
досить складних виробів), де “пропускні здатності” ребер – це
час, за яке потрібно з декількох вузлів виробу (вершин графа)
одержати інший (більше складний) вузол. Набагато більший
інтерес представляє мережі зв'язку, де пропускні здатності
ребер – це звичайно “кількість одночасних повідомлень”, які
можуть передаватися між комп’ютерами (вершинами графа).
Потоком у мережі між вершиною t (джерелом) і s
(стоком) називається набір чисел сij, (тобто кількість
умовного “вантажу”, перевезеного з вершини з номером i у
вершину з номером j), що задовольняють чотирьом умовам:
1) числа с ij  0, причому якщо с ij > 0, то с ji = 0 (немає
зустрічних перевезень);
2) числа cij  qij (відповідних пропускних здатностей
ребер);
3) якщо вершина з номером i – проміжна (не збігається із
джерелом і стоком), то

74