Графы. Теоретическое знакомство (первые начинания)

Тема графов — это интересная, полезная и пугающая тема. Теория графов — "Ужас студента". Алгоритмы на графах — потрясающий ум людей их открывших.

Что такое граф? Чтобы ответить на этот вопрос своим читателям, я буду описывать тему немного по-своему.
Граф — это множество объектов.
В большинстве задач это однотипные объекты. (Множество городов или множество домов, или множество людей, или множество чего-то ещё однотипного)

Чтобы решать задачи с таким множеством, нужно каждый объект из этого множества обозначить как что-то. Общепринято это самое что-то называть вершинами графа.

Описывать графы и основные определения удобно рисунками, поэтому для чтения этой страницы рисунки должны быть включены.

Графы

Графы

Графы

Графы Графы E обычно называют пару вершин. В двумерном массиве этой пароя часто выступают номер строки + номер столбца. По номеру строки и номеру столбца проверяют соединение, и если оно есть на пересечении, то это обозначают в значениях массива (матрицы) в месте пересечения строки и столбца

Графы

Графы

Графы

Графы На этом рисунке у графа одни только ребра. Ребра на графе обозначают обычными отрезками, хотя можно показать стрелочками, но сути это не изменит, потому как направление двустороннее. Такой граф называется неориентированным
Графы Иногда можно увидеть граф, в котором дорога ведет в ту же точку, откуда выходит. Такая дорога называется петлей. На рисунке изображена петля и понять что это, не должно быть сложно.
Графы У графа могут быть два маршрута или более, которые начинаются в одной и той же вершине и заканчиваются в другой, но оба маршрута заканчиваются в одной и той же другой вершине. Рисунок скорее всего хорошо демонстрирует этот момент. Такие маршруты (дуги, ребра) называются кратными.
Графы Вы часто будете встречать понятия смежности и инцендентности. На рисунке голубым цветом отмечены две вершины, которые соединены ребром друг с другом. Такие вершины называют смежными.
Графы Вы часто будете встречать понятия смежности и инцендентности. На рисунке красным цветом отмечены два ребра, которые идут в одну точку. Такие ребра, как и вышеописанные вершины, тоже называются смежными.
Графы Вы часто будете встречать понятия смежности и инцендентности. Если объекты вершина и вершина однотипны, если объекты дорога и дорога однотипны, то объекты вершина и дорога не очень-то и однотипны, но чтобы обозначить связь вершины и дороги, существует понятие инцендентности. Т.е. это принадлежность вершины графа к маршруту графа, если маршрут принадлежит вершине графа (стыкуется с ней), то маршрут и вершина инцендентны.
Графы Так как в графе может существовать такая вершина, к которой нет маршрутов, то для такой вершины существует понятие — изолированная вершина.
Графы Этот рисунок уже был самым первым. Но для такой ситуации существует определение — нуль-граф.
Графы Для решения некоторых задач и для изучения примеров, нужно знать, что такое полный граф. Полный граф — это такой граф, из любой вершины которого существует прямая связь с любой и с каждой другой вершиной этого графа.
Графы Если для какой-то из вершин не существует прямого маршрута хотя бы в одну из других вершин графа, то такой граф неполный.

Многое не описано, но эта часть информации может быть кому-то поможет.

13 комментариев на «“Графы. Теоретическое знакомство (первые начинания)”»

  1. Спасибо большое за краткое и главное понятное объяснение основных понятий связанных с графами!

  2. Аноним:

    как делать БЛЕАТЬ

  3. ministrel:

    Спасибо большое! Хорошая информация!

  4. Artem:

    все очень круто объяснено, спасибо:)

  5. Мария:

    Спасибо за хорошее объяснение!

  6. Аноним:

  7. VasiaLisa:

    Четко, понятно

  8. Дмитрий:

    Круто! Много сразу стало понятным.

  9. Аноним:

    Для начинающих  написано очень доходчиво и вовсе не страшно.Спасибо.

  10. flyant:

    Так КРУТО мне не объяснили даже преподаватели в вузе. Спасибо большое. Читать приятно. Всё понятно. Очень четко, кратко, ёмко.

  11. Даниил:

    Очень крутое обьяснение,преподы вообще

  12. Дмитрий:

    Огромное спасибо!!! Крайне доходчиво!!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/vandad-nahavandipur/ios-priemy-programmirovaniya/?lfrom=15589587
Яндекс.Метрика