Бипартитивни граф — разлика између измена
Садржај обрисан Садржај додат
Спашавам 1 извора и означавам 0 мртвим. #IABot (v2.0beta8) |
|||
Ред 41:
За један чвор, степен је број грана који улазе и излазе из њега и означава се са '''deg(V)'''. Сума степена за бипартитивне графове је:
Низ степени бипартитивног графа је пар листи где свака садржи степене два дисјунктна скупа. На пример бипартитивни граф К3,5 има низ степени '''(5, 5, 5), (3, 3, 3, 3, 3)'''. Изоморфни бипартитивни граф има исти низ степени. Али низ степени не мора у општем случају да јединствено описује бипартитивни граф; у неким случајевима, неизоморфни бипартитивни графови такође могу да имају тај низ степени.
Пробелем реализације бипартиције је проблем налажења једноставног бипартитивног графа са низом степена представљен као две листе природних бројева. (Пратеће нуле могу да се игноришу јер су тривијално реализоване додавањем одговарајућег броја изолованих чворова диграфу.)
| |||