✖


Jump to content

Таблица крупнейших известных графов заданного диаметра и максимальной степени

    Add links

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

    Таблица порядков крупнейших известных графов неориентированной задачи степенного диаметра

    [ редактировать ]

    Ниже приведена таблица номеров вершин для наиболее известных графов (по состоянию на июль 2022 г.) в неориентированной задаче степенного диаметра для графов степени не выше 3 ≤ d ≤ 16 и диаметра 2 ≤ k ≤ 10. Лишь некоторые из Известно, что графики в этой таблице (выделены жирным шрифтом) являются оптимальными (т. е. максимально возможными). Остальные — это всего лишь самые большие из обнаруженных на данный момент, и, таким образом, поиск большего графа, который по порядку (с точки зрения размера набора вершин) ближе к границе Мура, считается открытой проблемой . Известны некоторые общие конструкции для значений d и k, выходящих за пределы диапазона, указанного в таблице.

    к
    д
    		2 3 4 5 6 7 8 9 10
    3 10 [г 1] 20 [г 2] 38 [г 3] 70 [г 4] 132 [г 5] 196 [г 5] 360 [г 6] 600 [г 5] 1250 [г 7]
    4 15 [г 2] 41 [г 8] 98 [г 5] 364 [г 9] 740 [г 10] 1 320 3 243 7 575 17 703
    5 24 [г 2] 72 [г 5] 212 [г 5] 624 2 772 [г 11] 5 516 17 030 57 840 187 056
    6 32 [г 12] 111 [г 5] 390 1404 7 917 [г 11] 19 383 76 461 331 387 [г 13] 1 253 615
    7 50 [г 14] 168 [г 5] 672 [г 15] 2 756 [г 16] 11 988 52 768 249 660 1 223 050 6 007 230
    8 57 [г 17] 253 [г 18] 1 100 5 060 39 672 [г 19] 131 137 734 820 4 243 100 24 897 161
    9 74 [г 17] 585 [г 9] 1 550 8 268 [г 13] 75 893 [г 11] 279 616 1 697 688 [г 13] 12 123 288 65 866 350
    10 91 [г 17] 650 [г 9] 2 286 13 140 134 690 [г 19] 583 083 4 293 452 27 997 191 201 038 922
    11 104 [г 5] 715 [г 9] 3 200 [г 20] 19 500 156 864 [г 20] 1 001 268 7 442 328 72 933 102 600 380 000
    12 133 [г 21] 786 [г 19] 4 680 [г 22] 29 470 359 772 [г 11] 1 999 500 15 924 326 158 158 875 1 506 252 500
    13 162 [г 23] 856 [г 24] 6 560 [г 20] 40 260 531 440 [г 20] 3 322 080 29 927 790 249 155 760 3 077 200 700
    14 183 [г 21] 916 [г 19] 8 200 [г 20] 57 837 816 294 [г 11] 6 200 460 [г 25] 55 913 932 600 123 780 7 041 746 081
    15 187 [г 26] 1 215 [г 27] 11 712 [г 20] 76 518 1 417 248 [г 20] 8 599 986 90 001 236 1 171 998 164 10 012 349 898
    16 200 [г 28] 1 600 [г 27] 14 640 [г 20] 132 496 [г 27] 1 771 560 [г 20] 14 882 658 [г 25] 140 559 416 2 025 125 476 12 951 451 931

    Записи без сносок были найдены Loz & Širáň (2008) . Во всех остальных случаях сноски в таблице указывают начало координат графа, достигающего заданного числа вершин:

    1. ^ Петерсена График .
    2. ^ Перейти обратно: а б с Оптимальные графы доказали свою оптимальность Эльспасом (1964) .
    3. ^ Оптимальный график, найденный Доти (1982) и доказанный Бусетом (2000) .
    4. ^ График найден Алегре, Фиолом и Йеброй (1986) .
    5. ^ Перейти обратно: а б с д и ж г час я Графики, найденные Джеффри Эксу с 1998 по 2010 год.
    6. ↑ График найден Цзяньсяном Ченгом в 2018 году.
    7. ^ График найден Кондером (2006) .
    8. ^ График найден Олрайтом (1992) .
    9. ^ Перейти обратно: а б с д Графики найдены Делормом (1985a) .
    10. ^ График найден Комелласом и Гомесом (1994) .
    11. ^ Перейти обратно: а б с д и Графики, найденные Пинедой-Виллависенсио и др. (2006) .
    12. ^ Оптимальный граф, найденный Вегнером (1977) и доказанный Молодцовым (2006) .
    13. ^ Перейти обратно: а б с Графики найдены Канале и Родригесом (2012) .
    14. ^ Граф Хоффмана-Синглтона .
    15. ^ График найден Сампелсом (1997) .
    16. ^ График найден Диннином и Хафнером (1994) .
    17. ^ Перейти обратно: а б с Графики найдены Сторвиком (1970) .
    18. ^ График найден Маргаридой Митхана и Франческом Комелласом в 1995 году и независимо Сампелсом (1997) .
    19. ^ Перейти обратно: а б с д Графики найдены Гомесом (2009) .
    20. ^ Перейти обратно: а б с д и ж г час я Графики найдены Гомесом и Фиолом (1985) .
    21. ^ Перейти обратно: а б Графики найдены Делормом и Фархи (1984) .
    22. ^ График найден Бермондом, Делормом и Фархи (1982) .
    23. ^ Графики Маккея-Миллера-Ширана, найденные Маккеем, Миллером и Шираном (1998) .
    24. ↑ График найден Владом Пелахатым в 2021 году.
    25. ^ Перейти обратно: а б Графики найдены Гомесом, Фиолом и Серрой (1993) .
    26. ^ График найден Эдуардо А. Канале в 2012 году.
    27. ^ Перейти обратно: а б с Графики найдены Делормом (1985b) .
    28. ^ График найден Абасом (2016) .

    Ссылки

    [ редактировать ]
    • Абас, Марсель (2016), «Графы Кэли диаметра два с порядком более 0,684 границы Мура для любой степени», European Journal of Combinatorics , 57 : 109–120, arXiv : 1511.03706 , doi : 10.1016/j.ejc. 2016.04.008
    • Комеллас, Франческ; Гомес, Хосе (1994). «Новые большие графы с заданной степенью и диаметром». arXiv : математика/9411218 .
    • Доти, Карл (1982), «Большие регулярные межсетевые сети», Труды 3-й Международной конференции по распределенным вычислительным системам , Компьютерное общество IEEE, стр. 312–317.
    • Эльспас, Бернард (1964), «Топологические ограничения на логику, ограниченную межсоединениями», 1964 г., Труды Пятого ежегодного симпозиума по теории коммутационных цепей и логическому проектированию , стр. 133–137, doi : 10.1109/SWCT.1964.27
    • Гомес, Хосе (2009), «Некоторые новые большие (Δ, 3)-графы», Networks , 53 (1): 1–5, doi : 10.1002/NET.V53:1
    • Гомес, Хосе; Фиол, Микель (1985), «Плотные составные графы», Ars Combinatoria , 20 : 211–237.
    • Молодцов, Сергей (2006), Общая теория передачи информации и комбинаторика , стр. 853–857, ISBN.  978-3-540-46244-6
    • Сэмпелс, Майкл (1997), «Большие сети малого диаметра», Теоретико-графовые концепции в информатике , Конспекты лекций по информатике, том. 1335, Springer, Берлин, Гейдельберг, стр. 288–302, doi : 10.1007/BFb0024505 , ISBN.  978-3-540-69643-8
    [ редактировать ]
    Retrieved from "https://en.wikipedia.org/w/index.php?title=Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree&oldid=1212629739"
    Arc.Ask3.Ru: конец переведенного документа.
    Arc.Ask3.Ru
    Номер скриншота №: cf934a4dfd655216ab4892bf62cafb74__1709920860
    URL1:https://arc.ask3.ru/arc/aa/cf/74/cf934a4dfd655216ab4892bf62cafb74.html
    Заголовок, (Title) документа по адресу, URL1:
    Table of the largest known graphs of a given diameter and maximal degree - Wikipedia
    Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)