«Связность» в случайно сгенерированных графах

Question

Последние 3-4 дня я играл с реализацией графиков и связанных с ними структур в python. среди прочего, у меня есть тривиальная функция для генерации случайных графов, то есть графов, в которых две вершины связаны с заданной вероятностью. затем графики отображаются с использованием graphviz.

Во всяком случае, в ходе вышеуказанной деятельности я заметил, что выше определенной вероятности почти все графы с заданным количеством вершин всегда связаны. пара вопросов:

• Существуют ли другие "свойства", которые проходят через аналогичный "переход"?
• Я уверен, что кто-то еще, должно быть, изучил все это более строго. какие-нибудь указатели?

Answer 1

Хороший вопрос!

Фактически, тема случайных графов хорошо известна и восходит к Эрдосу и Реньи, 1959.

Наблюдение за порогом также превосходно.Есть и другие свойства графиков, которые разделяют этот «пороговый» феномен.

Фактически доказано, что большинство "монотонных" свойств имеют это свойство "порога".Это было доказано Эрдосом и Реньи (согласно книге, упомянутой ниже).

Свойство P является монотонным, если граф H на n вершинах имеет P, подразумевает любой суперграф G (на n вершинах) из H (т.е. Hявляется подграфом G) также имеет P. Например, гамильтонов цикл является одним из таких свойств.Связность - это другое.

Примечание: это определение монотонности может отличаться от других текстов по теории графов.Я упоминаю один из приведенных в книге ниже.

Книга Беллы Боллобаса Случайные графики * должна помочь вам начать.См. Стр. 40 для обсуждения монотонных свойств, имеющих «порог».Я должен предупредить вас, что в этой книге используется довольно тяжелая математика.