hoppá! há ez gráfelmélet! a feladatra adott válasz: a síkbarajzolhatóság: síkbarajzolható a gráf, ha gömbre rajzolható. ez a sztereografikus projekció. összefüggő síkbarajzolható gráfnak n csúcsa e éle és t tartománya van ( a síkbarajzolható gráf a síkot tartományokra osztja) akkor eleget tesz az Euler-formulának, azaz: n-e+t=2 ha ez nem teljesül, akkor a gráfot nem lehet lerajzolni a síkba úgy, hogy az éle ne messék egymást:)
egy ellenpélda: a Kuratowksi-gráfok nem síkbarajzolható gráfok K5 és a K3,3
Kibogozós izé... úgy kell elrendezni a bogyókat, hogy egy vonal se keresztezzen egy másikat.
egy ellenpélda: a Kuratowksi-gráfok nem síkbarajzolható gráfok K5 és a K3,3