Wikipédia

„Mycielski-konstrukció” 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
bevezetés módosítása
a →‎Definíció: link hozzáadása
2. sor:
 
==Definíció==
A Mycielski-konstrukció a <math>V(G)=\{v_1,...,v_n\}</math> csúcshalmazú <math>G</math> [[gráf]]hoz egy olyan <math>M(G)</math>-vel jelölt gráfot rendel, melyben [[feszített részgráfkéntrészgráf]]ként szerepel a <math>G</math> gráf, továbbá még n+1 csúcs. Ezek a következő elrendezésben: Minden <math>G</math>-beli <math>v_i</math> csúcsnak van egy <math>u_i</math> párja, melynek szomszédsága megegyezik a <math>v_i</math> szomszédságával, vagyis azokkal és csak azokkal a csúcsokkal van összekötve, amelyekkel <math>v_i</math>. Az (n+1)-edik új csúcs (<math>w</math>) mindegyik <math>u_i</math> csúccsal össze van kötve, de egyetlen <math>v_i</math>-vel sincs.
Mycielski-gráfoknak azokat a gráfokat nevezzük, amelyek a két csúcsú [[Teljes_gráf|teljes gráfból]], vagyis a két pontból és egyetlen élből álló gráfból előállíthatóak a fenti eljárás egymás után következő véges számú alkalmazásával.
 
9. sor:
Az ábrán az alsó öt csúcs által feszített részgráf az <math>M_3</math>-mal izomorf, az ábrán jelölt többi csúccsal alkotja az <math>M_4</math>-et.
 
Megjegyzés: Az <math>M_4</math>-et [[Grötzsch-gráf]]nak is szokás nevezni.
 
 
==Tétel==
A lap eredeti címe: „https://hu.wikipedia.org/wiki/Mycielski-konstrukció”