Поняття про граф

Для вирішення багатьох задач, може бути застосоване таке поняття, як граф.

Граф-це множина точок (вершин), які з’єднані між собою лініями, що називаються дугами або ребрам.

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

Розв’язання:Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх। Якщо двоє знайомі, то з’єднаємо їх відрізком (ребром). Виявляється, що така ситуація не тільки можлива, але й може описуватися декількома схемами.

Тобто можна сказати, що граф-це сукупність об’єктів, зв’язками між якими служать ребр. Приклади графів з декількома вершинами та ребрами.

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