„Girth” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: pt:Cintura (teoria dos grafos) |
a r2.5.2) (Bot: következő módosítása: es:Cintura (teoría de grafos); kozmetikai változtatások |
||
1. sor:
A [[gráfelmélet]]ben egy [[gráf]] '''girth paramétere''' ''k''
Ha a gráf nem tartalmaz kört ([[Erdő (gráfelmélet)|erdő]]) akkor a '''girth paramétere''' végtelen.
A girth szakszónak nincs bejáratott magyar fordítása, néha a kissé komolytalan bár szellemes „derékbőség” kifejezést is használják rá.
Tetszőleges ''k'' ≥ 2
== Példák ==
* Egy n hosszú kör girth-paramétere n.
* Egy négyzetrács-gráf girth paramétere 4.
* Minden G gráf girth paramétere 3, ha [[klikkszám]]a legalább 3.
* Speciálisan <math>K_n</math> girth-paramétere 3 ha <math>n \geq 3</math>
* A [[Petersen-gráf]] girth paramétere 5.
== A girth paraméter és a [[kromatikus szám]] kapcsolata ==
Ha egy gráf girth-paramétere nagyobb mint 3, akkor a gráf háromszögmentes.
20. sor:
Az általánosabb állítást, miszerint tetszőleges ''a'' és ''b''-re létezik ''a'' girth-paraméterű és ''b'' kromatikus számú gráf, [[Erdős Pál]] bizonyította először a valószínűségi módszer segítségével.
== Források ==
Angol Wikipédia [http://en.wikipedia.org/wiki/Girth_(graph_theory) Girth]
28. sor:
[[en:Girth (graph theory)]]
[[es:
[[fr:Maille (théorie des graphes)]]
[[pl:Obwód grafu]]
| |||