Подання графів

Граф- є безліч вершин (вузлів) і ребер, які з'єднує пару різних вершин. Описуватимемо граф масивом вузлів nodes, кожен з яких містить масив go з номерами вузлів, в які можна перейти безпосередньо з даного. На відміну від списків та дерев, графи мають складну топологію, тому для їхньої візуалізації необхідно задати координати 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 перевертає у вузлі від одного до ribs ребер:

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

Наведемо код цієї функції: Функція createTri(num, k0, k1, k2) усередині трикутника, утвореного вершинами k0, k1, k2 рекурсивно num разів повторює трикутник Серпінського:

Модифікований трикутник Серпінського можна отримати функцією createTriangle2:

У вже побудованому графі, функція delRibs (prob, ribs) з ймовірністю prob у кожному вузлі ліквідує від одного до ribs ребер (з рівномірним розподілом). Нижче наведено приклад скрипта g.createGrid(50, 20, 10); g.delRibs(0.7, 1):

Клас Graph

Створення та зміна графів

Для роботи з графами необхідно підключити два модулі: graph.js і draw.js (графічне відображення).

clone (graph) - задати граф за іншим графом або масивом вузлів graph
create (nNodes, r) - створити граф незв'язних nNodes вузлів, розташованих по колу радіуса r
addNode (go, nm) - додати вузол, повернувши його номер, вказавши, за необхідності масив ребер go та ім'я nm
addRib(i, j) - додати ребро, направлене з вузла під номером i у вузол j
bind (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) - створити граф у вигляді 6-кутової решітки шириною w вузлів і висотою h вузлів з довжиною ребра len (px);
createTriangle (num, len) - створити граф у вигляді трикутника Серпінського з числом рекурсій num та стартовим ребром len
createTriangle2 (num, len) - створити граф у вигляді модифікованого трикутника Серпінського з числом рекурсій num та стартовим ребром len
createHole (x, y, r) - видалити вузли всередині кола радіуса r з центром в x, y (у вже існуючому графі)
delRibs (prob, ribs) - видалити у вузлі з ймовірністю prob від одного до ribs ребер (з рівною ймовірністю)
insertNode (i, j, pos) - вставити вузол у ребро між двома вузлами, додавши його, якщо ребра не було. При pos = 0.5 (за умовчанням) вузол вставляється посередині ребра. У випадку pos=[0. 1]
swapRibs (prob, ribs) - з ймовірністю prob перевертає у вузлі від одного до ribs ребер
set (par, val) - встановити кожному вузлу графа властивість par значення val
createOn () - створити в кожному вузлі масиви ребер on: []
createDist() - створити в кожному вузлі масиви довжин ребер d: [], використовуючи координати вузлів
translate (dx,dy) - зрушити координати вузлів на dx,dy
scale (sx,sy) - змінити масштаб для координат вузлів у sx,sy разів