bookmate game
Клауди Альсина

Мир математики. Том 11. Карты метро и нейронные сети. Теория графов

Сообщить о появлении
Загрузите файл EPUB или FB2 на Букмейт — и начинайте читать книгу бесплатно. Как загрузить книгу?
  • Ариана Пехцитирует2 года назад
    Хорошо да коротко — вдвойне хорошо.

    Народная мудрость
  • Anna Dцитирует6 лет назад
    Можно ли найти такой путь в связном графе, который бы проходил через все вершины графа только один раз, причем начальная и конечная вершины при этом совпадали? Такие пути называют гамильтоновыми циклами.
  • Anna Dцитирует6 лет назад
    Подсчитать число ребер полного графа Кn очень просто: каждая вершина должна соединяться с n — 1 вершиной, число вершин равно n, следовательно, значение выражения n(n — 1) будет равно удвоенному числу ребер (так как каждое ребро соединяет две вершины). Поэтому общее число ребер будет равно n(n — 1)/2 — биномиальному коэффициенту , равному числу всех возможных пар на множестве из n элементов. Зависимость между числом ребер и n является квадратичной, следовательно, число ребер Кn будет возрастать очень быстро.
  • Anna Dцитирует6 лет назад
    Критерий существования эйлерова цикла выражен теоремой, которая звучит так:

    «Связный граф содержит эйлеров цикл тогда и только тогда, когда все его вершины имеют четную степень».
  • Anna Dцитирует6 лет назад
    В связном графе эйлеровым циклом называется путь, содержащий все ребра графа, начальная и конечная вершины которого совпадают. При этом вершины могут повторяться, а ребра — нет.
  • Anna Dцитирует6 лет назад
    Раскраска вершин V(С) графа G множеством цветов С состоит в присвоении каждой вершине графа цвета из множества С таким образом, что смежные вершины будут окрашены в разные цвета. Хроматическое число X(G) графа G определяется так: это минимальное количество цветов, в которое можно раскрасить вершины графа С так, чтобы любые смежные вершины имели разные цвета.
  • Anna Dцитирует6 лет назад
    «Граф является планарным тогда и только тогда, когда он не содержит ни одного подграфа, гомеоморфного К3,3 или К5».

    Чтобы определить, является ли граф планарным, нужно удалить все вершины степени 2 и проверить, не содержит ли полученный граф К3,3 или К5.
  • Anna Dцитирует6 лет назад
    «Плоский граф с вершинами степени 3 можно раскрасить тремя красками тогда и только тогда, когда все его грани ограничены четным числом ребер».
  • Anna Dцитирует6 лет назад
    «Карту можно раскрасить двумя цветами тогда и только тогда, когда в соответствующем ей графе все вершины имеют четную степень».

    Любопытно, что если карту можно раскрасить двумя цветами, то все вершины соответствующего графа будут иметь четную степень. Если в нем будет хотя бы одна вершина с нечетной степенью, то как минимум одна грань графа будет граничить с двумя гранями и для раскраски понадобится уже три цвета.
fb2epub
Перетащите файлы сюда, не более 5 за один раз