Бипартитивни граф — разлика између измена

Садржај обрисан Садржај додат
Нема описа измене
Нема описа измене
Ред 47:
 
=== Веза са хиперграфовима и усмереним графовима ===
[[Матрица повезаности]] бипартитивног графа '''(U, V, E)''' је '''(0,1)'''-матрица величине''' |U| X |V|''' који има један за сваки пар повезаних чворова и нулу за несуседне чворове. Матрица повезаности може да се користи и да би се описала еквиваленција између бипартитивних графова, хиперграфова и усмерених графова.
 
Хиперграф је комбинаторијална структура таква, као и неусмерени граф, има чворове и гране, али у којима гране могу да буту произвољни скупови чворова и грана које имају идентичне крајеве. Бипартитивни граф''' (U, V, E)''' може да се користи да би се моделовао хиперграф у које је '''U''' скуп чворова хиперграфа, '''V''' је скуп хиперграна, и '''Е''' садржи гране од чворо хиперграфа до гране хиперграфа. Ако ово узмемо у обзир, матрица повезаности бипартитивног графа је баш инцидентна матрица одговарајућих хиперграфова. Као специјалан случај овог одговарајања измешу бипартитивних графова и хиперграфова, било који мултиграф (граф у којем постоји две или више гране између два иста чвора) може да буде интерпретиран као хиперграф у којем неке хипергране имају исте крајеве, и представљене су помоћу бипартитивног графа који нема вишеструке повезаности и у којем су чворови на једној страни степена два.