Графично представяне

Графика- е набор от върхове (възли) и ръбове, който свързва двойка различни върхове. Ще опишем графиката чрез масив от възли, всеки от които съдържа масив с номерата на възлите, до които можете да отидете директно от дадения. За разлика от списъците и дърветата, графиките имат сложна топология, така че за да ги изобразите, трябва да посочите координатите x и y на всеки възел. Възелът може също да бъде наречен nm и да съхранява други данни. Графиката се реализира от класа Graph. Може да се зададе на друга графика или масив от възли, както в този пример:

Друг начин за създаване на графики в класа Graph е да зададете броя на неговите възли и след това постепенно да добавите ръбове:

Повечето алгоритми трябва само да знаят възлите, до които можете да отидете от дадения. В някои случаи обаче е необходима обратна информация - масив от възли, от които можете да влезете в дадения. Такива on масиви (на всеки възел) се изграждат от go масиви с помощта на функцията g.createOn(). Като цяло един възел може да има следните свойства: По подразбиране цветът на възела е Graph.svg.cFill="#FFC". Ако е даден масивът от цветове Graph.svg.colors и възелът е означен с chk, тогава той се боядисва с номера на цвета chk от този масив. Друг начин за оцветяване на възли и ръбове е директно задаване на свойствата col и cols на всеки възел.

Малко определения

Еднопосочното ребро на графика понякога се наричадъга, а двупосочното се наричаправо. Граф, състоящ се от V възли (== върхове), съдържа най-много V (V-1) ребра (броейки двупосочно ребро като две ребра). Два графа се наричат изоморфни, ако тяхната топология (броят на възлите и начините на тяхното свързване) съвпада до имена на възли.

Пътятна графика е набор от върхове, които могат да бъдат достигнати последователноедин по един. Ако всички върхове и ръбове, които образуват път, са различни, тогава той се наричапрост път. Под върховете 0,1,2 съставляват пътя.Цикъле прост затворен път (започващ и завършващ в един и същи връх. На втората снимка е 1,3,4:

Граф, състоящ се от двупосочни ръбове, се наричасвързан, ако има път от всеки възел до всеки друг възел. Ако има еднопосочни ръбове, може да няма път (по-висок, например от 4 до 0), но този график все още е свързан. Несвързаният граф се състои от набор от свързани (вътре в себе си) подграфи.Ацикличнатаграфика не съдържа цикли вътре (нарича се ощегора). Ако в ацикличен граф има един възел, от който можете да стигнете до всеки друг (и по уникален начин), тогава такъв граф се нарича дърво.

Хамилтонов пъте прост път, преминаващ презвсекивъзел на графиката веднъж.Ойлеров път- преминава презвсекиръб точно веднъж.

Някои компютърни задачи, свързани с графики:

Намиране на най-краткия път.
Намиране на най-дългия път.
Проверка на графика за свързаност.
Търсете Хамилтонов път (или доказателство за липсата му).
Потърсете пътя на Ойлер (или доказателство за липсата му).
Проверка на изоморфизма на два графика (тяхната идентичност без отчитане на имената на възлите и техните координати).
Планарност на графиката (способността да се начертае в равнина без пресичане на ръбове и върхове).
Оцветяване на възлите на графиката в k цвята, така че нито едно ребро да не свързва възли от един и същи цвят.

Генериране на големи графики

Не е лесно да се определят големи графики по "ръчен" начин, следователно за тестване на алгоритми е удобно да се генерират произволни графики.размер. Например, решетка с ширина w възли и височина h възли с дължина на ръба len (в пиксели) се създава от createGr >(w,h,len, oneway). Четвъртият аргумент във функцията (ако присъства и е равен на true) прави ръбовете на графиката насочени. По-долу са дадени три опции за използване на тази функция. В третия случай, когато чертаете графика, показването на имена на възли е деактивирано ( Graph.svg.showNm = false). Във втория случай функцията g.swapRibs(prob, ribs) с вероятност prob преобръща възела от един към ребра ръбове:

Друга, по-"пропусклива" опция е графика под формата на триъгълник на Сиерпински createTriangle (num, len) с брой рекурсии num и начален ръб с дължина len (в px):

Ето кода на тази функция: Функцията createTri(num, k0, k1, k2) вътре в триъгълника, образуван от върховете k0, k1, k2 рекурсивно повтаря триъгълника на Сиерпински num пъти:

Модифицираният триъгълник на Сиерпински може да бъде получен с помощта на функцията createTriangle2:

Във вече изградената графика функцията delRibs (prob, ribs) елиминира от едно до ребра ръбове във всеки възел с вероятност prob (с равномерно разпределение). По-долу е примерен скрипт g.createGrid(50, 20, 10); g.delRibs(0,7, 1):

Графичен клас

Създаване и модифициране на графики

За да работите с графики, трябва да свържете два модула: graph.js и draw.js (графичен дисплей).

клонинг (граф) - дефинирайте график от друг график или масив от възли на графика
create (nNodes, r) - създаване на графика на несвързани възли nNodes, разположени в кръг с радиус r
addNode (go, nm) - добавяне на възел чрез връщане на неговия номер, като по избор указва масив от go ръбове и името nm
addRib (i, j) - добавяне на ръб, насочен от възел i към възел j
свързване (i, j) - добавяне на двустранен ръб между възлите подчислата i и j
delRib (i, j) - премахване на ръба, насочен от възел i към възел j
delNode (i) - изтриване на възел номер i
fullConnect () - свържете с ръбове всички възли с всички
createGr >(w,h, len, oneway) - създаване на графика под формата на решетка с ширина от w възли и височина от h възли с дължина на ръба от len (в px); ако е зададен oneway, тогава ръбовете са еднопосочни
createHex (w,h, len) - създаване на графика под формата на шестоъгълна решетка w възли широки и h възли високи с дължина на ръба len (в px);
createTriangle (num, len) - създаване на графика на триъгълник на Сиерпински с брой рекурсии и len начален ръб
createTriangle2 (num, len) - създаване на модифицирана графика на триъгълник на Сиерпински с брой рекурсии и len начален ръб
createHole (x,y, r) - премахване на възли вътре в кръг с радиус r с център x,y (във вече съществуваща графика)
delRibs (prob, ribs) - премахване от един до ребра ръбове във възел с вероятност prob (с еднаква вероятност)
insertNode (i, j, pos) - вмъкнете възел в ръб между два възела, като го добавите, ако няма ръб. При pos = 0,5 (по подразбиране), възелът се вмъква в средата на ръба. Като цяло pos=[0. 1]
swapRibs (prob, ribs) - с вероятност prob обръща във възел от един към ребра ръбове
set (par, val) - задайте свойството par на всеки графичен възел на val
createOn () - създаване на масиви от ръбове, включени във всеки възел на: []
createDist() - създава масиви от дължини на ръбове d: [] във всеки възел, като използва координатите на възела
translate (dx,dy) - транслиране на координатите на възлите чрез dx,dy
scale (sx,sy) - променете мащаба за координатите на възлите по sx,sy пъти