Графи, їх види

Якщо фігура має безліч вершин і ребер, причому кожна деталь укладена двома вершинами, то її називають графом.

Якщо кілька графів з’єднати разом, то можна отримати дерево. Важливо, щоб з’єднання графів не зациклюватися операції.

Графи можуть бути різних видів:

Якщо граф має спрямованість, то його називають орієнтованим. Тобто важливий порядок. Наприклад, спочатку необхідно вимити руки і тільки потім їсти, а не навпаки, тобто важливий порядок дій.

Якщо ребра графа різні за важливістю, то такий граф називають зваженим. Наприклад, при складанні алгоритмів деякі лінії можуть бути коротше, а інші довші. Причому біля кожної стоїть цифра. Наприклад, ви хочете купити комп’ютер, якщо ви підете в магазин біля будинку, то заплатите 100 тисяч рублів, якщо ж в центрі міста, то 150 тисяч рублів. Якби даний алгоритм був написаний за допомогою зваженого графа, то гілочка, ведуча до покупки комп’ютера біля будинку, була б коротше.

Якщо граф об’єднує кілька перерахованих видів графа, то його можна назвати повним.

Псевдографом – граф, в якому є не пряма ребра.

Теорія графів

  • Якщо вершини послідовно з’єднуються ребрами, то їх називають маршрутом. Маршрут повинен мати тільки один напрямок.
  • Якщо ж в маршруті ребра не перетинаються, то його називають шляхом.
  • Якщо шлях замкнутий, то він носить назву циклу.
  • Якщо при відсутності деякого ребра граф ділитися на кілька компонент, то це ребро називається мостом.
  • Якщо вершина має тільки одне ребро, то вона називається висячої.
  • Якщо певний шлях проходить кожну вершину, причому один раз, то його називають Гамільтона шляхом.
  • Якщо маршрут проходить по всіх ребрах раз, то його називають ейлеровим маршрутом.
  • Якщо в деякій задачі є послідовність, що складається з випадкових чисел, але при цьому її можна обчислити за допомогою логічних міркувань або формул, то така послідовність називається псевдослучайной. Прикладом псевдослучайной послідовності може злучити рівняння руху.
Посилання на основну публікацію