„Gráfelméleti fogalomtár” változatai közötti eltérés

a
 
== Gráfok lerajzolása ==
Egy gráf '''diagram'''ja alatt, az absztrakt gráf valamilyen képi megjelenítését értjük (lásd a példa gráfot).
 
Egy gráf '''beágyazása''' egy felületbe, ha csúcsait elhelyezzük a felületen, majd berajzoljuk a csúsok közti éleket. Egy '''metszéspont''', vagy ''élkereszteződés'' egy egymást metsző élpár. Egy gráf ''lerajzolható'' egy felületre, ha a gráf csúcsai és élei elrendezhetőek rajta metszéspontok nélkül., azaz ha van metszésmentes felületbe ágyazása.
<!-- The genus of a graph is the lowest genus of any surface on which the graph can embed. -->
 
Egy gráf '''[[síkbarajzolható gráf|síkbarajzolható]]''' (''síkgráf''), ha van síkbarajzolása. Egy síkgráfot egy adott síkbarajzolásával együtt '''síkbarajzolt gráf'''nak hívunk. A példa gráf síbarajzolható, bizonyítja ezt az ábrán látható egyik lehetséges síkbarajzolása; az ''n'' pontú teljes gráf nem rajzolható síkba ha ''n'' > 4; de például minden fa síkbarajzolható.
 
[[Image:Nonisomorphicdualgraps.png|thumb| Különböző síkbarajzolásokhoz különböző duális tartozik (csak a felső duálisban van 6-fokú pont)]]
Egy síkbarajzolás '''tartomány'''okra (''lap'') osztja a síkot, néhány véges és egy végtelen, ún. '''külső''' tartományra. Két tartományt '''szomszédos'''nak hívunk, ha van közös határoló élük. Egy síkbarajzolt ''G'' gráf duálisa'''duális gráf'''ja (jelölése ''G''<sup>*</sup>) egy olyan gráf, melynek csúcsai ''G'' tartományai (beleértve a külső tartományt); és minden ''G''-beli élnek megfelel egy él ''G''<sup>*</sup>-ban, úgy hogy a duálisbeli él azt a két (nem feltétlenül különböző) csúcsot köti össze amelyek az eredeti él szomszédos tartományai. Vegyük észre, hogy két csúcs akkor és csak akkor szomszédos ''G''<sup>*</sup>-ban, ha a megfelelő tartományok szomszédosak ''G''-ben. Egy ''G'' síkgráf duálisa mindig egy síkbarajzolható ''multigráf'' (gondoljunk például a háromszög duálisára), de speciális esetben lehet egyszerű gráf is (például ''K''<sub>4</sub>, amely izomorf a duálisával, azaz ''önduális''). Minden 3-szorosan összefüggő egyszerű síkgráf (amely szükségképpen izomorf egy ''P'' konvex [[poliéder]] élhálójával) duálisa egy szintén 3-szorosan összefüggő egyszerű síkgráf (mely izomorf a duális poliéder, ''P''<sup>*</sup> élhálójával).
{{csonk-szakasz}}
<!--
(Bármely síkgráf izomorf egy konvex poliéder élhálójának részgráfjával (→sztereografikus projekció)
 
Furthermore, since we can establish a sense of "inside" and "outside" on a plane, we can identify an "outermost" region that contains the entire graph if the graph does not cover the entire plane. Such outermost region is called an outer face. An outerplanar graph is one which can be drawn in the planar fashion such that its vertices are all adjacent to the outer face; and an outerplane graph, one which is drawn in such fashion.
 
-->
 
Egy gráf'''metszési szám'''a (jelölése cr(''G'')) a ''G'' beágyazásai közül a legkevesebb metszéspontot tartalmazó metszéspontjainak száma.
 
A ''G'' gráf '''vastagság'''a azon síkgráfok minimális száma, amennyi már elegendő ''G'' lefedéséhez.
 
== Súlyozott gráfok és hálózatok ==
321

szerkesztés