Wikipédia

„Páros gráf” változatai közötti eltérés

Laptörténet interaktív böngészése
[nem ellenőrzött változat][nem ellenőrzött változat]
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Kristofh (vitalap | szerkesztései)
78 szerkesztés
Nincs szerkesztési összefoglaló
Kristofh (vitalap | szerkesztései)
78 szerkesztés
Nincs szerkesztési összefoglaló
1. sor:
{{korr}}
[[Image:Simple-bipartite-graph.svg|thumb|Példa egy páros gráfra]]
Akkor nevezünk egy <math>G</math> gráfot párosnak, ha <math>G</math> csúcsainak halmazát fel tudjuk úgy osztani egy <math>A</math> és <math>B</math> halmazra, hogy az összes <math>G</math>-beli élre teljesül, hogy az egyik végpontja <math>A</math>-ban van, a másik pedig <math>B</math>-ben. Egy <math>G</math> páros gráfot következőképpen jelölünk: <math>G</math> <math>=</math> <math>(A,B)</math>.
23 ⟶ 22 sor:
====Bizonyítás:====
 
Egy <math>G</math> páros gráfnak minden feszített reszgráfja is páros gráf, ezért elég belátni, hogy minden páros gráfgráfra <math>\omega(G)</math> <math>=</math> perfekt<math>\chi(G)</math>. Ez triviálisan igaz, ugyanis egy páros gráf háromszögmentes, ás<math>\omega(G)</math> <math>=</math> <math>\chi(G)</math>s ha legalább egy éle van akkor <math>\omega(G)</math> <math>=</math> <math>2</math> és <math>\chi(G)</math> <math>=</math> <math>2</math>. Ha nincs éle a gráfnak, akkor pedig <math>\omega(G)</math> <math>=</math> <math>\chi(G)</math> <math>=</math> <math>1</math>.
 
== Lásd még ==
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Páros_gráf”