Izomorf gráfok - studopediya
Két grafikonok, amelyek egymástól csak a számozás a csúcsok és az élek nevezzük izomorfak.
Azok eltérhetnek grafikus ábrázolása, és a szomszédsági mátrix és előfordulását. Annak érdekében, hogy a két grafikon - ez egy és ugyanaz a grafikonon, ez szükséges és elégséges annak megállapításához, 1-1 levelezés közöttük.
Előfeltételei két grafikon izomorfak:
1 azonos számú csúcsok és az élek
2. csomópontjain diagram ugyanolyan mértékben.
De a végrehajtás ezen tulajdonságok nem elégséges feltétele a gráfizomorfizmus.
Példa: Construct gráf izomorf a grafikon az előző példában.
Path és ciklus a grafikonon
Egy út egy gráf egy sorozata élek vezető csúcstól csúcsig.
Egy ciklus egy olyan út, amely a végső és kezdeti csúcsok egybeesnek. A ciklus egyszerű, ha átmegy egyik csúcsa egyszerre.
Hosszú ciklus élek számát is.
Ha számít az összes egyszerű ciklust páros hosszúságú, akkor a grafikon nincs ciklus páratlan hosszúságú.
Gráf egy egyszerű ciklus akkor és csak akkor, ha minden csúcsának a fokszáma 2.
Amikor eltávolítja a grafikon egyik szélétől lehet kapni mind a csatlakoztatott és a leválasztott grafikon.
Él AB nevezzük hídon. ha eltávolítják csúcsokat A és B diszjunktak.
Amennyiben bármelyik széle van a híd
1. A szélén AB egy híd, ha AB az egyetlen út csatlakozási csomóponton B.
2. AB egy híd, ami él AB nem minden ciklusban.
3. AB. egy hídon, ha két csúcs a C1 és C2 úgy, hogy az út áthalad azok összekötő AB.