В прошлый раз мы говорили о теории графов и ее многочисленных приложениях, в том числе о том, что такое простой граф. На этот раз мы рассмотрим их структуру и свойства.
Чтобы убедиться, что мы все находимся на одной странице, давайте кратко рассмотрим, что такое график и какой график мы будем рассматривать в этом уроке.
Граф представляет собой набор точек (или вершин) и отношений между ними. Мы будем рассматривать графы, которые являются простыми (что означает, что каждая пара вершин имеет не более одного ребра, и ни одно ребро не возвращается к вершине, с которой оно началось), неориентированными (что означает, что ребрам не задано направление) и невзвешенным. (это означает, что ребра не имеют разницы в важности).
Для вас, любителей математики, мы не будем говорить здесь о нулевых графах (графах без вершин) или бесконечных графах (графах с бесконечным числом вершин). Это крайние случаи, и вы точно не увидите их на своем GPS.
Если вам трудно понять это определение или вы все еще не понимаете, что такое граф, то я рекомендую прочитать последний пост в блоге на эту тему, чтобы освежить вашу память, прежде чем читать остальную часть этой статьи.
Теперь, когда у нас есть общее представление о том, что такое граф, давайте рассмотрим некоторые свойства, которыми могут обладать графы.
Графики могут быть соединены или разъединены. Связный граф связан, а несвязный граф — нет. Это, казалось бы, определение мусора имеет немного меньшее определение мусора. По сути, если вершина может быть соединена с другой вершиной через путь в графе, то этот граф связан. В противном случае граф несвязен.
Чтобы прочитать это, давайте прочитаем символы один за другим. Первый символ, ∀, означает «для любого» на английском языке. Затем идет x, переменная. Символ ∈ обозначает «в», а V — множество всех вершин графа. Таким образом, «∀ x ∈ V» означает «для любой вершины x». Точно так же «∀ z ∈ V» означает «для любой вершины z». «∃» означает «существует». «x−z» не является вычитанием. На самом деле, это даже не близко. «x−z» обозначает путь от x до z. Наконец, «∈ G» означает «в G», где G — граф.
Все предложение означает: «для любых двух вершин x и z существует путь из x в z в графе».
Определение отключения является противоположным. Обычно мы просто добавляем «¬» перед оператором. Символ обозначает «логическое не».
Иногда говорят, что граф ацикличен. Ациклический граф не имеет циклов. Ваша типичная карта связана, но не ациклична: вы можете побегать по своему району, чтобы доказать это. Позвольте мне сделать это прямо сейчас…
Пант, Пэн… Кажется, я слишком устал, чтобы продолжать… Но в следующий раз мы поговорим о деревьях, лесах и Дымчатом Медведе (шучу).
