Gráfok lexikografikus szorzata

A matematika, azon belül a gráfelmélet területén a G és H gráfok lexikografikus szorzata vagy gráfkompozíció egy gráfszorzás, olyan kétváltozós gráfművelet, amely gráfok rendezett párjaihoz egy új gráfot rendel. A $G ∙ H$ vagy $G[H]$ lexikografikus szorzat olyan gráf, melyre a következők igazak:

$G ∙ H$ csúcshalmaza megegyezik a $V(G) \times V(H)$ Descartes-szorzattal;
két $G ∙ H$ -beli csúcs, $(u, v)$ és $(x, y)$ pontosan akkor szomszédosak, ha $u$ szomszédos $x$ -szel $G$ -ben vagy $u = x$ és $v$ szomszédos $y$ -nal $H$ -ban.

Ha a két gráf élrelációi rendezési relációk, akkor lexikografikus szorzatuk élrelációja éppen a megfelelő lexikografikus rendezés.

A lexikografikus szorzatot elsőként Felix Hausdorff (1914) tanulmányozta. Ahogy (Feigenbaum & Schäffer 1986) megmutatta, annak eldöntése, hogy egy gráf lexikografikus szorzatként előáll-e, a gráfizomorfizmus-problémával ekvivalens.

Tulajdonságok

A lexikografikus szorzat általában nemkommutatív: $G ∙ H \neq H ∙ G$ . A diszjunkt unió művelettel együtt azonban disztributívak: $(A + B) ∙ C = A ∙ C + B ∙ C$ . Ezen kívül teljesít egy a komplementerképzéssel kapcsolatos azonosságot: $C(G ∙ H) = C(G) ∙ C(H)$ .

A lexikografikus szorzat függetlenségi száma könnyen adódik tényezőinek függetlenségi számaiból (Geller & Stahl 1975):

α(G ∙ H) = α(G)α(H)

.

A lexikografikus szorzat klikkszáma is multiplikatív:

ω(G ∙ H) = ω(G)ω(H)

.

A lexikografikus szorzat kromatikus száma megegyezik G frakcionális színezés szerinti b-szeres kromatikus számával, ahol b megegyezik H kromatikus számával:

χ(G ∙ H) = χ b (G)

, ahol b = χ(H).

Két gráf lexikografikus szorzata pontosan akkor perfekt gráf, ha mindkét tényező perfekt (Ravindra & Parthasarathy 1977).

Fordítás

Ez a szócikk részben vagy egészben a Lexicographic product of graphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

Feigenbaum, J. & Schäffer, A. A. (1986), "Recognizing composite graphs is equivalent to testing graph isomorphism", SIAM Journal on Computing 15 (2): 619–627, DOI 10.1137/0215045.
Geller, D. & Stahl, S. (1975), "The chromatic number and other functions of the lexicographic product", Journal of Combinatorial Theory, Series B 19: 87–95, DOI 10.1016/0095-8956(75)90076-3.
Hausdorff, F. (1914), Grundzüge der Mengenlehre, Leipzig
Imrich, Wilfried & Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
Ravindra, G. & Parthasarathy, K. R. (1977), "Perfect product graphs", Discrete Mathematics 20 (2): 177–186, DOI 10.1016/0012-365X(77)90056-5.

További információk

Weisstein, Eric W.: Graph Lexicographic Product (angol nyelven). Wolfram MathWorld