Розріз графа - це

Розріз графа в задачах про потік - така пара множин вершин (S, T), що

1. , де - безліч вершин графа
2. , де - витік, - стік.

Величиною розрізу називається сума пропускних спроможностей таких ребер, що.

Інші визначення розрізу (перетину) графа

• Розріз графа - безліч ребер, видалення яких ділить граф на два ізольованих подграфа, один з яких, зокрема, може бути окремим вузлом.
• Розріз графа - лінія, що ділить граф на дві незв'язані частини.

Характеристики

• Лінії перетину можуть перетинати довільне число ребер і хорд.
• Для отримання головного перетину графа потрібно лінію перетину графа провести таким чином, щоб вона перетинала тільки одну гілку графа при довільному перетині хорд.

Дивитися що таке "Розріз графа" в інших словниках:

Словник термінів теорії графів - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И К Л М Н О П Р С ... Вікіпедія

Вершина (граф) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Довжина шляху в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Дуга (теорія графів) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Инцидентность - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Мультіграф - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Подграф - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Простий шлях в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Шлях в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія