Прямое произведение графов

Декартово произведение или прямое произведение [1] G H графов G и H — это граф, такой, что

  • множество вершин графа G H — это прямое произведение V(G) × V(H)
  • любые две вершины (u,u') и (v,v') смежны в G H тогда и только тогда, когда
    • либо u=v и u' смежна v' в H
    • либо u' =v' и u смежна v в G.
Декартово произведение графов.

Декартово произведение может быть распознано эффективно за линейное время[2]. Операция является коммутативной как операция на классах изоморфизмов графов, и более строго, графы G H и H G естественно изоморфны, но операция не является коммутативной как операция на помеченных графах. Операция является также ассоциативной, так как графы (F G) H и F (G H) естественно изоморфны.

Обозначение G × H порой используется и для декартова произведения графов, но чаще оно используется для другой конструкции, известной как тензорное произведение графов. Символ квадратика чаще используется и является недвусмысленным для декартова произведения графов. Он показывает визуально четыре ребра, получающиеся в результате декартова произведения двух рёбер[3]

ПримерыПравить

  • Декартово произведение двух рёбер является циклом с четырьмя вершинами: K2   K2=C4.
  • Декартово произведение K2 и пути является лестницей.
  • Декартово произведение двух путей является решёткой.
  • Декартово произведение n рёбер является гиперкубом:
 
Таким образом, декартово произведение двух графов гиперкубов является другим гиперкубом — Qi   Qj=Qi+j.

СвойстваПравить

Если связный граф является декартовым произведением, его можно разложить единственным образом на произведение простых множителей, графов, которые нельзя разложить на произведение графов [4][5]. Однако, Имрих и Клавжар[6] описали несвязный граф, который можно представить двумя различными путями как декартово произведение простых графов:

(K1 + K2 + K22)   (K1 + K23)=(K1 + K22 + K24)   (K1 + K2),

где знак плюс означает несвязное объединение, а верхний индекс означает кратное декартово произведение.

Декартово произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным[7].

Декартово произведение является двудольным тогда и только тогда, когда каждый из его множителей является двудольным. Более обще, хроматическое число декартова произведения удовлетворяет уравнению

χ(G   H)=max {χ(G), χ(H)}[8].

Гипотеза Хедетниеми утверждает связанное равенство для тензорного произведения графов. Число независимости декартовых произведений непросто вычислить, но, как показал Визинг[5], число независимости удовлетворяет неравенствам

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G   H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

Гипотеза Визинга утверждает, что число доминирования декартова произведения удовлетворяет неравенству

γ(G   H) ≥ γ(G)γ(H).

Алгебраическая теория графовПравить

Алгебраическую теорию графов можно использовать для анализа декартова произведения графов. Если граф   имеет   вершин и   матрицу смежности  , а граф   имеет   вершин и   матрицу смежности  , то матрица смежности декартова произведения двух графов задаётся формулой

 ,

где   означает произведение Кронекера матриц, а   означает   единичную матрицу[9].

ИсторияПравить

Согласно Имриху и Клавжару[6] декартовы произведения графов определили в 1912 Уайтхед и Рассел. Произведение графов неоднократно переоткрывалось позже, в частности, Гертом Сабидусси[4].

ПримечанияПравить

  1. Визинг использовал термин «декартово произведение», в статье «Прямое произведение» то же произведение называется прямым.
  2. (Imrich, Peterin 2007). Для более ранних алгоритмов полиномиального времени см. статью Фейгенбаума, Хершбергерга и Шеффера (Feigenbaum, Hershberger, Schäffer 1985), а также статью Ауренхаммера, Хагауэра и Имриха(Aurenhammer, Hagauer, Imrich 1992).
  3. Hahn, Sabidussi, 1997.
  4. 1 2 Sabidussi, 1960.
  5. 1 2 Визинг, 1963.
  6. 1 2 Imrich, Klavžar, 2000.
  7. Imrich, Klavžar, 2000, с. Theorem 4.19.
  8. Sabidussi, 1957.
  9. Kaveh, Rahami, 2005.

ЛитератураПравить

СсылкиПравить