kapcsolat grafikon
Connected graph szétkapcsolt gráf csatlakoztatott komponens tulajdonságait
Irányítatlan gráf tekinthető csatlakoztatott, ha minden csúcsa az út bármely más csomóponttal (path lehet bármely élek számát). Példa: az alábbi ábra grafikon van csatlakoztatva. Azonban, mondjuk, ha törli egy él közötti csúcsok 4. és 5., akkor nem csatlakozik - a top 5 nem lesz képes, hogy bármely más csúcs.
Ha a csatlakoztatott tulajdonság nem megy végbe, egy grafikon az úgynevezett kapcsolt.
Továbbá, nem tartjuk multigráfokra, azaz grafikonok, amelyben két pont között két vagy több borda. Mi korlátozni az elemzést grafikonok, amelyben minden pontpár vagy nincsenek csatlakoztatva, vagy csatlakoztatva van egy szélét.
Ábrázolásához n csúcsú lett csatlakoztatva, ez kell legalább (n-1) szélei.
Ha a gráf legalább (n * n - 3n + 4) / 2 élek, akkor garantált, hogy koherens.
Ha a gráf összefüggő, az szükséges, hogy egy csúcs legalább 2 fok, azaz a csúcsok, amelyek mindegyike legalább két szomszédos csúcsot.
Ha a gráf összefüggő, és nem ciklus (vagyis a fa), az eltávolítása minden él vezet a csatlakozás megszakadása.
Disconnected grafikon áll csatlakoztatott komponensek. Csatlakoztatott komponens - a csúcsok halmaza úgy, hogy minden csúcsa ennek meg van a módja annak, hogy egy másik csúcsa ez a készlet, de egyik sem a tetején ez a készülék nem tud bejutni a csúcs kívül készlet. Nyilvánvaló, hogy az összeg a csúcsok száma a csatlakoztatott komponensek egyenlő a csúcsok száma.
Ábra mutatja a gráf két csatlakoztatott komponensek.
Figyeljük meg, hogy a csatlakoztatott komponens állhat egyetlen csúcs. Ha a számlálás n csúcsú, ez állhat több, mint n csatlakoztatott komponensek. Egy csatlakoztatott gráf összefüggő komponens csak.
Mindenesetre szétkapcsolt gráf csatlakoztatott komponens nem több, mint n -1 csomópontok. Ha tudja, hogy a gróf k csatlakoztatott komponensek, majd, hogy még szigorúbb értékelése: bármely csatlakoztatott komponens legfeljebb n-k + 1 csúcsot.
Ha szétkapcsolt gráf k csatlakoztatva komponenseket, így a csatlakoztatott gráf hozzáadni a grafikon a legalább k -1 borda.
Annak megállapítása, hogy egy gráf?
Válasszon egy csúcsából, és jelölje meg a meglátogatott (1), illetve a többi támaszkodnak még nem jártam (0):
A hinni a jelenlegi csúcs. Aztán a következőképpen kell eljárni. Jelölés látogatott szomszédos csúcsot: a jelenlegi top keres vele szomszédos, még nem látogatott, és jelölje meg őket, mint a meglátogatott.
Tegyük fel, hogy kiderült novopomechennyh k csúcsot (lásd éppen a 3). Az viszont választ közülük a jelenlegi és a rekurzív futtathatod jelölt látogatott csúcsa mellett is. A jelenlegi csomópont nem végez rekurziót, ha ez a csúcs nem szomszédos csúcsok, amelyek még nem jelölt, mint a meglátogatott.
Ha ezek után cselekvések minden csúcsot lesz jelölve a meglátogatott gráf összefüggő, vagy megszakad.
Nézzük egy kis példa:
Itt a tetején egy természetes szám, amit egy sor általa jelölve meglátogatott számú zöld szín azt jelenti, hogy a rekurzív hívás jött létre ez a csúcs.
Úgy döntött, egy csúcs (1). További jelölt három csúcsa vele szomszédos (2, 3, 4). Most válik az aktuális csomópont (2). A rekurzió: címke a két nem látogatott szomszédos csúcsot (5. és 6. számú). (5), rekurzió nem szükséges -, hogy nincs látogatott szomszédos csúcsot, a (6) rekurzió van szükség: jelöljük meg a 7-es számú 7 számot még nem látogatott meg „szomszéd” - a 8-as szám, és itt a 8. számú nem látogatott szomszédos csúcsot. Minden rekurzív hívások által generált vertex (2) befejeződött. Most a felső sorban (3), de nincs szükség a rekurziót. Bal vertex (4). Az egyik szomszédos csúcsok (9) nem jelzett, azt kijavítani. Összesen:
Következtetés: nem minden a legjobb látogatott Earl megjelent inkoherens.