„A számítástudomány alapjai - Segédanyagok a vizsgához” változatai közötti eltérés
| 312. sor: | 312. sor: | ||
** Egy gráfnak csak akkor létezik absztrakt duálisa, ha síkbarajzolható. | ** Egy gráfnak csak akkor létezik absztrakt duálisa, ha síkbarajzolható. | ||
** Egy gráf akkor és csak akkor gyengén izomorf egy másikkal, ha az alábbi három lépés ismételgetésével vele izomorf gráfot tudunk létrehozni: | ** Egy gráf akkor és csak akkor gyengén izomorf egy másikkal, ha az alábbi három lépés ismételgetésével vele izomorf gráfot tudunk létrehozni: | ||
**# Ha a gráfnak van olyan pontja, aminek elhagyásával a gráf két komponensre esne, akkor ezt a pontot megkettőzve "húzzúk szét" a gráfot két komponensre. | |||
**# Az előbbi lépés inverze: kétkomponensű gráfban mindkét komponensből válasszunk ki egy-egy pontot és ezeknél fogva "ragasszuk össze" a két komponenst. | |||
**# Ha a gráfnak van két olyan pontja, melyek elhagyásával a gráf két komponensre esne, akkor e pontokat megkettőzve "húzzúk szét" a gráfot két komponensre, gondolatban "tükrözzük" az egyik komponenst, majd a két pont mentén "ragasszuk össze" fordítva. | |||
* Ötszín-tétel: ha egy gráf síkbarajzolható, a kromatikus száma kisebb, vagy egyenlő, mint öt. | * Ötszín-tétel: ha egy gráf síkbarajzolható, a kromatikus száma kisebb, vagy egyenlő, mint öt. | ||
* Vizing-tétel: ha egy gráf egyszerű, akkor az élkromatikus száma kisebb, vagy egyenlő, mint a gráfban a legnagyobb előforduló fokszám plusz egy. | * Vizing-tétel: ha egy gráf egyszerű, akkor az élkromatikus száma kisebb, vagy egyenlő, mint a gráfban a legnagyobb előforduló fokszám plusz egy. | ||