Silný produkt grafů - Strong product of graphs

The králův graf, silný produkt dvou grafy cesty

v teorie grafů, silný produkt G ⊠ H grafů G a H je graf takový, že[1]

  • množina vrcholů G ⊠ H je kartézský součin PROTI(G) × PROTI(H); a
  • odlišné vrcholy (U u' ) a (v, v ' ) sousedí s G ⊠ H právě když:
    • u = proti a ty sousedí s proti' , nebo
    • ty = proti' a u sousedí s proti, nebo
    • u sousedí s proti a ty sousedí s proti' .

Je to svazek kartézský součin a tenzorový produkt.

Silný produkt se také nazývá normální produkt nebo A produkt.[Citace je zapotřebí ] Poprvé to představil Sabidussi v roce 1960.[2] V tomto nastavení je silný produkt v kontrastu s a slabý produkt, ale oba se liší pouze v případě, že jsou aplikovány na nekonečně mnoho faktorů.

Například králův graf, graf, jehož vrcholy jsou čtverce a šachovnice a jehož hrany představují možné tahy šachového krále, je silným produktem dvou grafy cesty.[3]

Při setkání s tímto termínem je třeba postupovat opatrně silný produkt v literatuře, protože se také používá k označení tenzorový součin grafů.[4]

Viz také

Reference

  1. ^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Grafy a jejich kartézský součin, A. K. Peters, ISBN  978-1-56881-429-2.
  2. ^ Sabidussi, G. (1960). "Násobení grafu". Matematika. Z. 72: 446–457. doi:10.1007 / BF01162967. hdl:10338.dmlcz / 102459. PAN  0209177.
  3. ^ Berend, Daniel; Korach, Efraim; Zucker, Shira (2005), „Dvoubarevné planární a související grafy“ (PDF), 2005 Mezinárodní konference o analýze algoritmů, Sborník diskrétní matematiky a teoretické informatiky, Nancy: Sdružení pro diskrétní matematiku a teoretickou informatiku, str. 335–341, PAN  2193130.
  4. ^ Viz strana 2 z Lovász, László (1979), „On the Shannon Capacity of a Graph“, Transakce IEEE na teorii informací, IT-25 (1): 1–7, doi:10.1109 / TIT.1979.1055985.