Dotová produktová reprezentace grafu - Dot product representation of a graph - Wikipedia

A tečkový součin jednoduchého grafu je metoda reprezentace a graf pomocí vektorových prostorů a bodového součinu z lineární algebra. Každý graf má reprezentaci tečkového produktu.^[1]^[2]^[3]

Definice

Nechat G být graf s množinou vrcholů PROTI. Nechat F být polem a F funkce z PROTI na F^k takhle xy je hrana G kdyby a jen kdyby F(X)·F(y) ≥ t. Toto je reprezentace tečkového produktu G. Číslo t se nazývá prahová hodnota produktu produktua nejmenší možná hodnota k se nazývá rozměr produktu tečka.^[1]

Vlastnosti

A prahový graf je bodový produktový graf s kladným součinem t a bodový produktový rozměr 1.^[1]
Každý intervalový graf má bodový produktový rozměr maximálně 2.^[1]
Každý rovinný graf má rozměr tečkového produktu maximálně 4.^[4]

Viz také

Matice sousedství

Reference

^ ^A ^b ^C ^d Fiduccia, Charles M .; Scheinerman, Edward R.; Trenk, Ann; Zito, Jennifer S. (1998), „Dot produktové reprezentace grafů“, Diskrétní matematika, 181 (1–3): 113–138, doi:10.1016 / S0012-365X (97) 00049-6, PAN 1600755.
^ Reiterman, J .; Rödl, V .; Šiňajová, E. (1989), „Vkládání grafů do euklidovských prostorů“, Diskrétní a výpočetní geometrie, 4 (4): 349–364, doi:10.1007 / BF02187736, PAN 0996768.
^ Reiterman, J .; Rödl, V .; Šiňajová, E. (1992), „O vkládání grafů do euklidovských prostorů malé dimenze“, Journal of Combinatorial Theory, Řada B, 56 (1): 1–8, doi:10.1016 / 0095-8956 (92) 90002-F, PAN 1182453.
^ Kang, Ross J .; Lovász, László; Müller, Tobias; Scheinerman, Edward R. (2011), „Dot produktové reprezentace rovinných grafů“, Electronic Journal of Combinatorics, 18 (1): Paper 216, PAN 2853073.

externí odkazy

Média související s Maticová reprezentace grafů na Wikimedia Commons

[fstz98-1] A ^b ^C ^d Fiduccia, Charles M .; Scheinerman, Edward R.; Trenk, Ann; Zito, Jennifer S. (1998), „Dot produktové reprezentace grafů“, Diskrétní matematika, 181 (1–3): 113–138, doi:10.1016 / S0012-365X (97) 00049-6, PAN 1600755.

[2] Reiterman, J .; Rödl, V .; Šiňajová, E. (1989), „Vkládání grafů do euklidovských prostorů“, Diskrétní a výpočetní geometrie, 4 (4): 349–364, doi:10.1007 / BF02187736, PAN 0996768.

[3] Reiterman, J .; Rödl, V .; Šiňajová, E. (1992), „O vkládání grafů do euklidovských prostorů malé dimenze“, Journal of Combinatorial Theory, Řada B, 56 (1): 1–8, doi:10.1016 / 0095-8956 (92) 90002-F, PAN 1182453.

[4] Kang, Ross J .; Lovász, László; Müller, Tobias; Scheinerman, Edward R. (2011), „Dot produktové reprezentace rovinných grafů“, Electronic Journal of Combinatorics, 18 (1): Paper 216, PAN 2853073.

[1]

[2]

[3]

[4]