Interested Article - Степень графа

Квадрат графа

Степень 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 .

Порождённые подграфы

K 4 как полуквадрат графа куба

двудольного графа G — это подграф графа G 2 , порождённый одной долей графа G . — это полуквадраты планарных графов , — это полуквадраты графов гиперкубов .

— это подграфы степеней деревьев, порождённые листьями деревьев .

Примечания

  1. , с. 82.
  2. Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
  3. , с. 370–382.
  4. , с. 654–662.
  5. , с. 1035–1052.
  6. , с. 422–426.
  7. , с. 189–213.
  8. , с. 1–10.
  9. Агнаррссон и Халлдорссон ( ) перечислили в своей статье публикации доказательства NP-трудности для случая общих графов, (статьи Маккормика (McCormick, 1983) и статьи Лина и Скиена (Lin, Skiena, 1995)), и для планарных графов (статьи Раманатхана и Ллойда (Ramanathan, Lloyd, 1992-1993)).
  10. , с. 105.
  11. , с. 323.
  12. .
  13. .
  14. , с. 81-88.
  15. , с. 238–249.
  16. , с. 127–138.
  17. .
  18. , с. 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 : .
Источник —

Same as Степень графа