Seznam grafů - List of graphs

Toto částečné seznam grafy obsahuje definice grafů a rodin grafů, které jsou známé pod určitými jmény, ale nemají vlastní článek na Wikipedii.

Pro shromážděné definice teorie grafů termíny, které neodkazují na jednotlivé typy grafů, jako např vrchol a cestaviz Glosář teorie grafů. Odkazy na existující články o konkrétních druzích grafů viz Kategorie: Grafy.

Ozubené kolo

G4

A převodový graf, označeno Gn je graf získaný vložením dalšího vrcholu mezi každou dvojici sousedních vrcholů na obvodu a graf kola Žn. Tím pádem, Gn má 2n+1 vrcholy a 3n hrany.[1] Grafy převodů jsou příklady squaregraphs, a hrát klíčovou roli v zakázaná charakterizace grafu squaregraphs.[2] Grafy převodů jsou také známé jako ozubená kola a bipartitní kola.

Mřížka

A mřížkový graf je graf jednotkové vzdálenosti odpovídající čtvercová mříž, takže to je izomorfní do grafu, který má vrchol odpovídající každé dvojici celých čísel (A, b) a spojující hranu (A, b) do (A+1, b) a (A, b+1). Graf konečné mřížky Gm, n je m×n obdélníkový graf izomorfní k grafu získanému omezením uspořádaných párů na rozsah 0 ≤ A < m, 0 ≤ b < n. Mřížkové grafy lze získat jako kartézský součin ze dvou cesty: Gm,n = Pm × Pn. Každý mřížkový graf je a střední graf.[3]

Kormidlo

A kormidelní graf, označeno Hn je graf získaný připojením jedné hrany a uzlu ke každému uzlu vnějšího obvodu a graf kola Žn.[4][5]

Humr

A humr graf je a strom ve kterém jsou všechny vrcholy ve vzdálenosti 2 od středu cesta.[6][7] Porovnat housenka.

Web

Webový graf Ž4,2 je krychle.

The web graf Žn,r je graf skládající se z r soustředné kopie graf cyklu Cn, s odpovídajícími vrcholy spojenými „paprsky“. Tím pádem Žn,1 je stejný graf jako Cn, a Žn, 2 je hranol.

Webový graf byl také definován jako hranolový graf Yn+1, 3, s odstraněnými okraji vnějšího cyklu.[5][8]

Viz také

Reference

  1. ^ Weisstein, Eric W. „Gear gear“. MathWorld.
  2. ^ Bandelt, H.-J .; Chepoi, V .; Eppstein, D. (2010), „Kombinatorika a geometrie konečných a nekonečných čtvercových grafů“, SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301
  3. ^ Weisstein, Eric W. "Mřížkový graf". MathWorld.
  4. ^ Weisstein, Eric W. "Helmův graf". MathWorld.
  5. ^ A b „Archivovaná kopie“ (PDF). Archivovány od originál (PDF) dne 31.01.2012. Citováno 2008-08-16.CS1 maint: archivovaná kopie jako titul (odkaz)
  6. ^ „Google Discussiegroepen“. Citováno 2014-02-05.
  7. ^ Weisstein, Eric W. "Humr". MathWorld.
  8. ^ Weisstein, Eric W. „Webový graf“. MathWorld.