Útvonalak, utak, láncok, ciklusok - stadopedia
Kérdések az ismétléshez
1. Mi a diszkrét matematika szakasza, amely a grafikonelméletet vizsgálja?
2. Mi a különbség az orientált és a nem irányított grafikonok között?
3. Adja meg a grafikon meghatározását?
4. Mi az incidencia viszony jelentése?
5. A grafikon helyi szintje?
6. Milyen esetekben vannak az izomorf grafikonok?
7. Melyek a grafikonok meghatározásának módjai?
8. Sorolja fel az incidencia mátrix és a szomszédsági mátrix közötti különbségeket?
9. Mikor egy grafikon egy grafikon része?
A grafikonelméletet tanulmányozó diszkrét matematika részlege megfontolásra kerül. A grafikonelmélet alapfogalmai, mint például csúcs, él, orientált gráf és így tovább. A helyi fokozat fogalmát adják meg. Megmutatják a grafikonok bemutatásának módját. Különösen a grafikon egyes részein végzett műveletek, valamint a grafikonok és bináris kapcsolatok tekinthetők.
Cél. különböző típusú grafikonszerkezetek tanulmányozására.
1 Tekintsük az útvonalra, az útvonalra, a láncra és a ciklusra vonatkozó fogalmakat a grafikonokra vonatkozóan.
2 Tekintsük a fa és az erdő grafikon szerkezetét.
Legyen G egy nem irányított grafikon.
A G-ben egy útvonal olyan M élek sorozata, amelyben minden két szomszédos él közös csúcspontja. Az útvonalon ugyanaz a él fordulhat elő többször is. Az út eleje a peremre eső csúcs, és nem az incidens; Az útvonal vége másodlagos és nem véletlenszerű. Ha többszörösek, további indikációra van szükség, amelyik a két incidens csúcs közül melyik tekinthető az útvonal elejének (végének).
Egy olyan útvonalat, amelyben kezdete és vége, azaz zárva van, egybeesik, ciklikusnak nevezik. Egy olyan útvonalat, amelyben az összes széle különbözik, láncnak nevezzük. Olyan lánc, amely nem metszik egymást, azaz amely nem tartalmaz ismétlődő csúcsokat, egyszerű láncnak nevezik.
A ciklikus útvonal ciklusnak nevezhető, ha ez egy lánc és egy egyszerű ciklus. ha ez egy egyszerű lánc.
A vertexek összekapcsolódnak, ha létezik egy M útvonal az elejével és a végével. Az útvonalhoz kapcsolódó csúcsokat egy egyszerű lánc is összekapcsolja. A csúcsok összekapcsolási viszonyának egyenértékű tulajdonságai vannak, és meghatározza a gráf csúcspontjainak partícióját diszjunktus részegységekké. Úgy tűnik, hogy a G grafikon kapcsolódik. ha minden csúcsa összekapcsolódik. Ezért a G () összes részgrafika kapcsolódik, és a grafikonhoz kapcsolódó összetevőknek nevezzük. Minden n-gráf egyedülállóan bomlik a csatlakoztatott komponensek közvetlen összegére
Legyen G egy orientált gráf.
Az élek szekvenciája, amelynél minden egyes előző él vége egybeesik a következő kezdetével, az úttá válik (ebben az irányban minden széle megy végig a tájoláson). Útközben ugyanaz a él fordulhat elő többször is. Az út kezdete az él kezdete, az út vége a szél végét jelenti.
Az útvonalat egy orientált láncnak (vagy egyszerűen egy láncnak) nevezik, ha mindegyik perem egyszerre egyszerre, és egy egyszerű láncban történik. ha bármelyik G csúcsa legfeljebb két éle felett van.
A vázlat az az út, amelyben. A kontúrot ciklusnak nevezik, ha lánc, és egy egyszerű ciklus, amikor egyszerű lánc. Ha a grafikon ciklusokat tartalmaz, akkor egyszerű ciklusokat tartalmaz. A ciklusokat nem tartalmazó grafikon aciklikusnak mondható.
A csúcsot csúcspontból elérhetővé lehet tenni, ha van egy út, amelynek kezdete és vége van.
A G digraphot hívják összekapcsolva, ha az ívek orientációját figyelembe véve kapcsolódik, és erősen kötődik, ha bármely csúcsról bármelyre létezik egy út.
Az útvonal (útvonal) éleinek számát hossza nevezi.
A csúcsok d (,) és az n-gráf közötti távolság egy egyszerű lánc minimális hossza az elejével és a végével. A középpont az n-gráf csúcspontja, amelyből a legmagasabb távolság a többi csúcsig minimális. A G középponttól a csúcsig terjedő maximális távolságot a r (G) gráf sugarának nevezzük.
Az Euler ciklus egy gráf ciklusa, amely a gráf összes széleit tartalmazza. Az Euler gráf egy Euler-ciklusú gráf (az Euler-ciklus a toll nyomvonalának tekinthető, amely a grafikon átlépése nélkül elhagyja a papírt).
Euler tétele. véges, irányítatlan G gráf Euler osztályokból, ha és csak akkor, ha csatlakozik, és az összes csúcsa egyenlő.
Az Euler-lánc egy olyan lánc, amely tartalmazza egy adott véges n-grafikon G széleit, de eltérő kezdet és vég. Annak érdekében, hogy a véges n-gráfban G létezik egy Euler-lánc, szükséges és elégséges ahhoz, hogy összekapcsolódjon, sőt minden csúcstalálkozó erejében, kivéve a kezdeti és a végleges (és páratlan erővel kell rendelkeznie). Annak érdekében, hogy az Euler-ciklus a végső digraph-ban létezzen, annak összefüggése szükséges és elégséges, valamint a grafikon csúcspontjainak egyenlőségét a bejövő és kimenő élekhez viszonyítva. .
A Hamilton-ciklus egy egyszerű ciklus, amely a vizsgált grafikon minden csúcsán halad át. A Hamilton-lánc egy egyszerű lánc, amely áthalad a gráf összes csúcsain, a különböző csúcsok elején és végében.