Interested Article - Степень графа
- 2021-02-01
- 2
Степень k (записывается G k ) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин , и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k . Для указания степени графа используется терминология, аналогичная степеням чисел — G 2 называется квадратом графа G , G 3 называется кубом .
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Свойства
Если диаметр графа равен d , то его d -ая степень является полным графом . Если семейство графов имеет ограниченную кликовую ширину , то это же верно и для d -х степеней графов семейства для любого фиксированного d .
Раскраска
Раскраску квадрата графа можно использовать для назначения частот участникам беспроволочной сети таким образом, чтобы никакие два участника не мешали бы друг другу и любому другому из общих соседей , а также для поиска графического представления графов с большим угловым разрешением .
Как хроматическое число , так и вырожденность k -ой степени планарного графа с максимальной степенью вершины Δ равны , где граница вырождения показывает, что можно использовать алгоритм жадной раскраски для раскраски графа таким числом цветов . Для случая квадрата планарного графа Вегнер в 1977 году высказал гипотезу, что хроматическое число такого графа не превышает , и на текущий момент известно, что хроматическое число не превышает . Более обще, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O ( d Δ), так что многие виды разреженных графов , отличные от планарных графов, также имеют пропорциональное Δ хроматическое число квадрата.
Хотя хроматическое число квадрата непланарного графа с максимальной степенью Δ может быть в худшем случае пропорционально Δ 2 , оно меньше для графов с большим обхватом и для этого случая ограничено числом O(Δ 2 /log Δ) .
Задача определения минимального числа цветов для раскраски квадратного графа NP-трудна даже для планарного случая
Гамильтоновость
Куб любого связного графа обязательно содержит гамильтонов цикл . Квадрат связного графа не обязательно будет содержать гамильтонов цикл и задача определения, что такой цикл содержится в квадрате, NP-полна . Тем не менее, согласно теореме Фляйшнера , квадрат вершинно 2-связного графа всегда гамильтонов .
Вычислительная сложность
Степень k графа с n вершинами и m рёбрами можно получить за время O( mn ) путём применения поиска в ширину , который осуществляется для каждой вершины графа с целью нахождения расстояний до всех других вершин. Альтернативно, если A — матрица смежности графа, модифицированная таким образом, что на главной диагонали не стоят нулевые элементы, то ненулевые элементы матрицы A k дают матрицу смежности k -ой степени графа , откуда следует, что построение k -ой степени графа может быть осуществлено за время, равное, с точностью до логарифмического множителя, времени умножения матриц .
Если граф задан, определение, не является ли он квадратом другого графа, является NP-полной задачей . Более того, NP-полной задачей является определение, является ли граф k -ой степенью другого графа для любого заданного числа k ≥ 2, а также является ли он k -ой степенью двудольнго графа для k > 2 .
Порождённые подграфы
двудольного графа G — это подграф графа G 2 , порождённый одной долей графа G . — это полуквадраты планарных графов , — это полуквадраты графов гиперкубов .
— это подграфы степеней деревьев, порождённые листьями деревьев .
Примечания
- , с. 82.
- Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
- , с. 370–382.
- ↑ , с. 654–662.
- , с. 1035–1052.
- , с. 422–426.
- , с. 189–213.
- , с. 1–10.
- Агнаррссон и Халлдорссон ( ) перечислили в своей статье публикации доказательства NP-трудности для случая общих графов, (статьи Маккормика (McCormick, 1983) и статьи Лина и Скиена (Lin, Skiena, 1995)), и для планарных графов (статьи Раманатхана и Ллойда (Ramanathan, Lloyd, 1992-1993)).
- , с. 105.
- , с. 323.
- .
- .
- , с. 81-88.
- , с. 238–249.
- , с. 127–138.
- .
- , с. 69–108.
Литература
- Adrian Bondy, U. S. R. Murty. . — Springer, 2008. — Т. 244. — (Graduate Texts in Mathematics). — ISBN 9781846289699 .
- Ioan Todinca. Coloring powers of graphs of bounded clique-width // Graph-theoretic concepts in computer science. — Springer, Berlin, 2003. — Т. 2880. — (Lecture Notes in Comput. Sci.). — doi : .
- Geir Agnarsson, Magnús M. Halldórsson. Coloring powers of planar graphs // Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00). — San Francisco, California, USA, 2000.
- M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F. T. Drawing graphs in the plane with high resolution // . — 1993. — Т. 22 , вып. 5 . — doi : .
- Florica Kramer, Horst Kramer. A survey on the distance-colouring of graphs // Discrete Mathematics . — 2008. — Т. 308 , вып. 2-3 . — doi : .
- Michael Molloy, Mohammad R. Salavatipour. A bound on the chromatic number of the square of a planar graph // Journal of Combinatorial Theory . — 2005. — Т. 94 , вып. 2 . — doi : .
- Noga Alon , Bojan Mohar. The chromatic number of graph powers // . — 2002. — Т. 11 , вып. 1 . — doi : .
- Polly Underground. On graphs with Hamiltonian squares // Discrete Mathematics . — 1978. — Т. 21 , вып. 3 . — doi : .
-
Reinhard Diestel.
10. Hamiltonian cycles
//
. — 2012.
- Рейнгард Дистель. Теория графов. — Новосибирск: Изд-во Ин-та математики, 2002. — ISBN 5-86134-101-X УДК 519.17 ББК 22.17.
- Richard Hammack, Wilfried Imrich, Sandi Klavžar. . — CRC Press, 2011. — (Discrete Mathematics and Its Applications). — ISBN 9781439813058 .
- R. Motwani, M. Sudan. Computing roots of graphs is hard // . — 1994. — Т. 54 . — P. 81–88. — doi : .
- Van Bang Le, Ngoc Tuy Nguyen. Hardness results and efficient algorithms for graph powers // Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers. — Berlin: Springer, 2010. — Т. 5911. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11408-3 . — doi : .
- Zhi-Zhong Chen, Michelangelo Grigni, Christos H. Papadimitriou. Map graphs // Journal of the ACM . — 2002. — Т. 49 , вып. 2 . — doi : .
- Shpectorov. On scale embeddings of graphs into hypercubes // . — 1993. — Т. 14 , вып. 2 . — doi : .
- N. Nishimura, P. Ragde, D.M. Thilikos. On graph powers for leaf-labeled trees // . — 2002. — Т. 42 . — doi : .
- 2021-02-01
- 2