„Gráfelméleti fogalomtár” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
→Összefüggőség: elvágó (''cut'') / elválasztó (''separating'') csúcs/él mizéria |
Kope (vitalap | szerkesztései) Nincs szerkesztési összefoglaló |
||
1. sor:
{{lektor}}
:''Ez a szócikk fordítással készül [[:en:Glossary_of_graph_theory]], de még csonk.''
A [[gráfelmélet]] a [[matematika]] egyik kutatási területe, a szakszókincse igen
==Alapfogalmak==
12. sor:
A gráfoknak más modelljei is vannak: például egy a csúcsok halmazán értelmezett bináris reláció (''→[[Gráf (halmazelmélet)]]''), vagy egy négyzetes, 0-kból és 1-kből álló mátrix.
Egy '''csúcs''' (alapelem) képe a diagramon egy pont, ezért hívják ''
Egy '''él''' (két alapelemből álló halmaz) képe a diagramon egy vonal, amely két csúcsot köt össze, ezeket '''végpont'''oknak hívjuk. Egy élet, melynek ''x'' és ''y'' a végpontjai ''xy''-nal jelölünk, azaz nincs köztük semmilyen szimbólum. A ''G'' gráf élhalmazának jelölése ''E''(''G''), vagy ''E'', ha nem okoz félreértést.
Egy '''hurokél''', vagy hurok egy olyan él, melynek két végpontja ugyanaz a csúcs. Egy él '''többszörös''', ha a gráfban van más él is ugyanezekkel a végpontokkal, egyébként az él '''egyszerű'''. Az '''él multiplicitás'''a azon (többszörös) élek száma melyekkel megegyeznek a végpontjai. Egy gráf egyszerű, ha nincsenek benne többszörös és hurokélek, multigráf, ha vannak többszörös élei, és multigráf vagy pszeudográf, ha többszörös élek és hurokélek is vannak benne (nincs egységes elnevezés az irodalomban). A gráf (megkülönböztető jelző nélkül) szinte mindig egyszerű gráfot jelöl, hacsak a szövegkörnyezet nem utal másra.▼
Két csúcs '''szomszédos''', ha éllel vannak összekötve.
Hasonlóan, két él '''szomszédos''', ha van közös csúcsuk. k
▲Egy '''hurokél''', vagy hurok egy olyan él, melynek két végpontja ugyanaz a csúcs. Egy él '''többszörös''', ha a gráfban van más él is ugyanezekkel a végpontokkal, egyébként az él '''egyszerű'''. Az '''él multiplicitás'''a azon (többszörös) élek száma melyekkel megegyeznek a végpontjai. Egy gráf '''egyszerű''', ha nincsenek benne többszörös és hurokélek, '''multigráf''', ha vannak többszörös élei, és multigráf vagy pszeudográf, ha többszörös élek és hurokélek is vannak benne (nincs egységes elnevezés az irodalomban). A gráf (megkülönböztető jelző nélkül)
A '''[[gráf címkézés]]'''e általában egyedi címkék (legtöbbször [[természetes szám]]ok) csúcsokhoz és élekhez rendelését jelenti. Ha egy gráf csúcsai, vagy élei címkézettek akkor címkézett gráfnak hívjuk, különben címkézetlennek. Különbséget tehetünk csúcscímkézett és élcímkézett gráfok között, ha hangsúlyozni szeretnénk, hogy csak a csúcs- vagy élhalmaz elemeit tekintjük megkülönböztethetőnek.
32. sor:
Három csúcsot '''háromszög'''nek hívunk, ha páronként össze vannak kötve, '''anti-háromszög'''nek, ha semelyik kettő nincs összekötve.
A ''G'' gráf
<!--eddig átnézve-->
Az egy csúcsponttal és nulla éllel rendelkező gráfot '''triviális gráf'''nak nevezzük, az olyan gráfot pedig, aminek csak csúcsai vannak, de nincsenek élei, '''élmentes gráfnak''', '''üres gráfnak''' vagy '''nullgráfnak''' (nincs konzisztens elnevezése az irodalomban). A csúcspont- és élmentes gráfot is szokás '''nullgráf'''nak vagy '''üres gráf'''nak nevezni, de nem minden matematikus fogadja el az ilyen gráf létezését.
| |||