Графиката се състои от върхове и ръбове. Върховете са свързани чрез ръбове според определено свойство - съотношението на инцидентност, което определя набора от ребра. В този случай могат да се образуват бримки и изолирани върхове.
Инструкция за употреба
1
Нека се даде набор от краища на графика и дадено отношение, чрез което човек може да начертае ръб от един връх към друг. Като пример, множеството от върхове {1, 2, 3, 4, 5, 6, 7, 8}, двете върхове x и y са в съотношение x + y <8.
2
Изградете матрица за съседство на връх. За да направите това, изградете квадратна таблица, броят на редовете и колоните в таблицата съответства на броя на върховете. След това поставете 1 в пресечната точка на i-тия ред и j-тата колона, ако върховете i и j удовлетворяват даденото съотношение. Поставете 0 в пресечната точка на i-тия ред и j-та колона, ако съотношението за съответните елементи не е изпълнено.
В нашия пример първият ред се попълва, както следва:
1 + 1 <8, така че в пресечната точка на 1-ви ред и 1-ва колона е 1
1 + 2 <8, отново 1
1 + 3 <8, отново 1
…
1 + 7 <8, неправилно неравенство, тогава този елемент на таблицата ще бъде 0
1 + 8 <8, отново 0
3
За да разберете броя на ръбовете, пребройте броя на единиците в матрицата на съседство, като не разделяте краищата.
В примера беше получена симетрична матрица, следователно първо единиците бяха изчислени над основния диагонал на матрицата (маркирани в синьо), а след това единиците върху основния диагонал (маркирани с червено). Общият брой на ребрата е 12.
4
Изградете матрица от инциденти (ръбове). За да направите това, нарисувайте таблица, броят на редовете в нея е равен на броя на върховете на графиката, а броят на колоните е равен на броя на ръбовете. Поставете единиците в линиите, които ще бъдат свързани чрез ръб. Краищата, водещи от върха към него, се наричат бримки и се добавят в края на матрицата. В колоните, съответстващи на бримките, има само една единица, за разлика от другите ръбове.
5
Сега нарисувайте графика. Подредете върховете на хартия произволно и ги свържете с ръбове, като използвате конструираните таблици. Върховете, които не са свързани с ръбове, се наричат изолирани.
Обърнете внимание
Фигурата показва ребрата за яснота. Обикновено теглото на реброто се пише над реброто.
