Pogovor:Polni graf
Izrek Kuratowskega je pomemben rezultat, a za ta članek PMSM ni bistven. Če pa je že notri v obliki
- »Ravninski graf ne more vsebovati (ali polnega dvodelnega grafa ) kot minorja«,
me zanima, kaj je to minor? --romanm (pogovor) 10:58, 22 oktober 2005 (CEST)
- To je verjetno podgraf, torej graf kjer iz katerega so odtranjene nekatere povezave.
- Ali ni to subdivizija? Sta minor in subdivizija sopomenki? Malo sem že pozabil, zvezkov pa nimam pri roki ... --romanm (pogovor) 09:57, 29 oktober 2005 (CEST)
Graf H=(U,F) je podgraf grafa G=(V,E), če je U podmnožica V in je F podmnožica E. Pozor! Pri tem je pomebno, da je (U,F) res graf! Vsaka izbira podmnožic U in F v splošnem ne določa grafa. Za vsako izbrano povezavo moramo izbrati tudi njeni krajišči.
- Hvala! V tem primeru minor ne more biti samo podgraf, ali pa je čisto zgornja trditev napačna, ker izrek Kuratowskega trdi več kot to, da graf ni ravninski, če obstaja podgraf ali . V poštev pride namreč (po spominu in z mahanjem rok) tudi odstranjevanje točk in dodelitev njihovih povezav sosedom (ali nekaj takega). --romanm (pogovor) 10:15, 29 oktober 2005 (CEST)
IZREK 1 (Kuratowski) Graf G je ravninski natanko takrat, ko ne vsebuje subdivizije K3,3 in ne subdivizije K5.
Naj bo e povezava grafa G. Naj S(G,e) označuje graf, ki ga dobimo tako, da povezavo e nadomestimo s potjo dolžine 2. Tej operaciji rečemo subdivizija povezave.
Če je F podmnožica EG, bo S(G,F) oznaka za graf, ki ga dobimo s subdivizijo vseh povezav iz F. Če je F=E, bomo drugi argument opustili in bo S(G) označeval subdivizijo grafa G.