Зада́ча сте́пеня — діа́метра — задача пошуку найбільшого можливого графа (в термінах розміру множини його вершин ) діаметром такого, що найбільший степінь будь-якої вершини в графі не перевищує . Розмір графа обмежений зверху межею Мура. Для і тільки граф Петерсена, граф Гофмана — Синглтона і, можливо, граф із діаметром і степенем досягають межі Мура. В загальному випадку графи з найбільшими значеннями степінь/діаметр мають розмір, значно менший від межі Мура.
Вивчається також задача пошуку найбільшого можливого орграфа, замість степеня графа в цьому випадку використовують напівстепень виходу.
Формула
Нехай — найбільше можливе число вершин графа зі степенем, що не перевершує
, і діаметром
, тоді
, де
— межа Мура:
Ця межа досягається в рідкісних випадках, тому вивчення пішло в напрямку, наскільки близькі до межі Мура існують графи.
Величину називають дефектом графа (тут
— число вершин у графі). Кажуть, що граф має малий дефект, якщо
. Є гіпотеза, що для степенів
не існує
-графів із дефектом 2. Про графи з дефектом, більшим від 2, відомо мало.
Для асимптотичної поведінки зауважимо, що .
Для параметра висловлено гіпотезу, що
для всіх
; відомо, що
і що
.
MaxDDBS
Якщо дано зв'язний граф-господар[] , верхня межа степеня
і верхня межа діаметра
, шукається найбільший підграф
графа
з найбільшим степенем, що не перевершує
і діаметром, що не перевершує
. Цю задачу називають MaxDDBS, і вона містить задачу розміру — діаметра як частковий випадок (а саме, якщо за граф-господар взяти досить великий повний граф). Задача є NP-складною.
Див. також
Примітки
- Молодцов, 2004, с. 109.
- Miller, 2010, с. 341.
- Miller, 2010, с. 337.
- Miller, 2010, с. 338.
Література
- Молодцов С. Г. Наибольшие графы диаметра 2 и степени 6 // Дискретный анализ и исследование операций : тезисы докладов. — Новосибирск, Академгородок : Институт математики им. С.Л. Соболева СО РАН, 2004. — Вип. 28 июня - 2 июля 2004 (27 червня). — С. 109. з джерела 10 квітня 2022. Процитовано 16 березня 2022.
- Bannai E., Ito T. On Moore graphs // J. Fac. Sci. Univ. Tokyo Ser. A. — 1973. — Т. 20 (27 червня). — С. 191–208.
- Hoffman Alan J., Singleton Robert R. Moore graphs with diameter 2 and 3 // IBM Journal of Research and Development. — 1960. — Т. 5, вип. 4 (27 червня). — С. 497–504. — DOI: . з джерела 18 травня 2008. Процитовано 16 березня 2022.
- Singleton Robert R. There is no irregular Moore graph // American Mathematical Monthly. — Mathematical Association of America, 1968. — Т. 75, вип. 1 (27 червня). — С. 42–43. — DOI: .
- Miller Mirka, Širáň Jozef. Moore graphs and beyond: A survey of the degree/diameter problem // . — 2005. — Т. Dynamic survey (27 червня). — С. DS14. з джерела 10 лютого 2022. Процитовано 16 березня 2022.
- . Архів оригіналу за 20 лютого 2012. Процитовано 16 березня 2022.
- Miller Mirka. An Overview of the Degree/Diameter Problem for Directed, Undirected and Mixed Graphs // Extended abstracts of IWONT. — Barcelona, 2010, 2010. — 27 червня. — С. 335—346.
- Dekker A., Perez-Roses H., Pineda-Villavicencio G., Watters P. The Maximum Degree & Diameter-Bounded Subgraph and its Applications // Journal of Mathematical Modelling and Algorithms. — 2012. — 27 червня. — DOI: .
- Miller M., Perez-Roses H., Ryan J. The Maximum Degree and Diameter Bounded Subgraph in the Mesh. Discrete Applied Mathematics. — 2012. — 27 червня. — DOI: .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет