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

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

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

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

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

Графы

Графы

Графы

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

Графы

Графы

Графы

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

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

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • Kulululu говорит:

    Thanks :mrgreen:




    0



    0
  • un1acker говорит:

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




    0



    0
  • Аноним говорит:

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




    0



    0
  • ministrel говорит:

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




    0



    0
  • Artem говорит:

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




    0



    0
  • Мария говорит:

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




    0



    0
  • Аноним говорит:




    0



    0

  • VasiaLisa говорит:

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




    0



    0
  • Дмитрий говорит:

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




    0



    0
  • Аноним говорит:

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




    0



    0
  • flyant говорит:

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




    0



    0
  • Даниил говорит:

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




    0



    0
  • Дмитрий говорит:

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




    0



    0

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

Ваш e-mail не будет опубликован.

Поиск

 
     

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

https://www.litres.ru/anatoliy-homonenko/visual-c-na-primerah-7068582/?lfrom=15589587
Яндекс.Метрика
НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Встречает в аду один черт другого и говорит: "Слушай, это ты того компьютерщика сюда притащил?" - "Да, а что?" - "Ты в другой раз толком объясняй, что такое ад - а то он, пока понял, что это не Doom, двести чертей перестрелял..."

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок