Графиката се състои от върхове и ребра. Върховете са свързани с ръбове според определено свойство - отношението на честотата, което определя множеството от ребра. В този случай могат да се образуват цикли и изолирани върхове.
Инструкции
Етап 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
Сега нарисувайте графика. Поставете върховете върху хартията по всякакъв начин и ги свържете с ръбове, като използвате изградените таблици. Върховете, които не са свързани с ръбове, се наричат изолирани.
