Mathematical Models of the Real World

Что такое идеальный расширитель?

Представьте себе сеть (граф), где узлы – это люди, а связи между ними – это дружеские отношения. В идеальном расширителе даже если вы берёте небольшую группу людей, они внезапно знакомы почти с каждым в этой сети. То есть, любая маленькая группа очень быстро «соединяется» со множеством других узлов сети. Это делает граф чрезвычайно «связанным», даже если у каждого узла сравнительно немного связей.

Например, если подумать о городе, где у всех мало дорог из каждого района, но любой район имеет прямые дороги к большому числу прочих районов, то информация (или люди) быстро распространяются по всему городу. Такой граф и называют идеальным расширителем.

Теория шести рукопожатий — это идея, согласно которой любой человек на Земле связан с любым другим через цепочку знакомых, которая в среднем состоит не более чем из шести ступеней.

1. Идеальный расширитель
Это тип регулярного графа, у которого каждая небольшая группа узлов имеет много связей с другими узлами. Это означает, что сеть очень хорошо «расширяется» несмотря на ограниченное число связей в каждой вершине.

Напомним: Регулярный граф — это граф, в котором все вершины имеют одинаковое количество соединений, то есть одинаковую степень. Например, если в графе каждая вершина связана ровно с тремя другими вершинами, то такой граф называют 3-регулярным или кубическим графом.

2. Гипотезы
Учёные долго спорили:
- Предполагалось, что идеальные расширители встречаются очень часто среди регулярных графов.
- Одна из гипотез была, что более 50% таких графов обладают нужными свойствами.

3. Новые результаты
Совсем недавно обнаружили, что около 69% всех регулярных графов являются идеальными расширителями. Это подтверждает, что свойства идеального расширения встречаются существенно чаще, чем изначально ожидали, и открывает новые возможности для применения этих свойств в разных областях науки, от квантовой механики до теории информации.

---

Статья на эту тему со ссылками https://www.securitylab.ru/news/558546.php

SecurityLab.ru

Один говорил «очень редко» , другой — «очень часто». 35-летний спор ученых о графах завершился неожиданностью

Что такое идеальные расширители и насколько они распространены?

👍3

www.tgoop.com/MathModels/1238

388 viewsApr 22 at 19:07

Что такое идеальный расширитель?

Представьте себе сеть (граф), где узлы – это люди, а связи между ними – это дружеские отношения. В идеальном расширителе даже если вы берёте небольшую группу людей, они внезапно знакомы почти с каждым в этой сети. То есть, любая маленькая группа очень быстро «соединяется» со множеством других узлов сети. Это делает граф чрезвычайно «связанным», даже если у каждого узла сравнительно немного связей.

Например, если подумать о городе, где у всех мало дорог из каждого района, но любой район имеет прямые дороги к большому числу прочих районов, то информация (или люди) быстро распространяются по всему городу. Такой граф и называют идеальным расширителем.

Теория шести рукопожатий — это идея, согласно которой любой человек на Земле связан с любым другим через цепочку знакомых, которая в среднем состоит не более чем из шести ступеней.

1. Идеальный расширитель
Это тип регулярного графа, у которого каждая небольшая группа узлов имеет много связей с другими узлами. Это означает, что сеть очень хорошо «расширяется» несмотря на ограниченное число связей в каждой вершине.

Напомним: Регулярный граф — это граф, в котором все вершины имеют одинаковое количество соединений, то есть одинаковую степень. Например, если в графе каждая вершина связана ровно с тремя другими вершинами, то такой граф называют 3-регулярным или кубическим графом.

2. Гипотезы
Учёные долго спорили:
- Предполагалось, что идеальные расширители встречаются очень часто среди регулярных графов.
- Одна из гипотез была, что более 50% таких графов обладают нужными свойствами.

3. Новые результаты
Совсем недавно обнаружили, что около 69% всех регулярных графов являются идеальными расширителями. Это подтверждает, что свойства идеального расширения встречаются существенно чаще, чем изначально ожидали, и открывает новые возможности для применения этих свойств в разных областях науки, от квантовой механики до теории информации.

---

Статья на эту тему со ссылками https://www.securitylab.ru/news/558546.php

BY Mathematical Models of the Real World