A főbb típusai a grafikonok
Típusú grafikonok határozza meg az általános elveket építése, míg a speciális esetekben a grafikon függ a különböző tulajdonságok a csúcsok és élek.
A grafikon az úgynevezett páros. ha a beállított csúcsához feloszthatjuk két részhalmaza úgy, hogy nem él nem csúcsokat összekötő azonos részhalmaza.
1. példa: építeni egy teljes páros gráf.
Teljes páros gráf álló két csúcsa és az összes lehetséges kapcsolatnak a tetején egy sor, hogy egy másik csúcsot (lásd alább).
Tehát Euler gráf egy grafikont, amely akkor kap körül a csúcsok és egyidejűleg átadni egy éle csak egyszer. Ebben minden csúcsában kell csak páros számú élek.
2. példa: Egy teljes gráf ugyanannyi n élek, ami az eset, hogy minden csúcsba, egy Euler gráf? Magyarázza meg a választ. Adjon példát.
Válasz. Ha n - páratlan szám, minden csúcsa esemény n -1 bordák. Ebben az esetben a gráf egy Euler gráf. Ilyen az alábbi ábrákat.
Rendszeres gráf összefüggő gráf minden csúcsának ugyanolyan k. Így például a 2. ábra mutat be példát, reguláris gráf, az úgynevezett mértéke a csúcsok rendszeres és 4-2-reguláris grafikonok vagy szabályos grafikonok 4. fokú és 2. fokú.
A csúcsok száma egy szabályos k-ik foka nem lehet kevesebb, mint k 1. Szabályos grafikonja páratlan fokú csak páros számú csúcsot.
3. példa Beépített reguláris gráf, amelyben a legrövidebb ciklus hossza 4.
Határozat. Érvelt, hogy annak érdekében, hogy ciklus hosszát az előre meghatározott feltétel teljesül, az szükséges, hogy a csúcsok száma a négy többszöröse. Ha a csúcsok száma egyenlő négy, kapsz egy grafikon látható az alábbi ábrán. Rendszeres, de ez a legrövidebb ciklus hossza 3.
Növekszik a csúcsok száma nyolc (a következő négy többszöröse). Mi csatlakoztassa a felső széle, hogy milyen mértékben csúcsok egyenlő három. Kapunk az alábbi grafikon kielégítő körülmények között a probléma.
Hamilton gráf egy grafikon, amely egy Hamilton-kör. A Hamilton-kör egy egyszerű hurok, amely áthalad a csúcsot egy grafikonon. Így, egyszerűen szólva, Hamilton grafikon - egy grafikon, amely lehet megkerülni a csúcsok és minden csúcs csak egyszer megismételjük feltérképezése során. Példa Hamilton-gráf - az alábbiakban.
4. példa a páros gráf, ahol n - a csúcsok száma a több A. és m - a csúcsok száma, amely több B, amely esetben a gráf Euler grafikon, és ebben az esetben - Hamilton-gráf?
Válasz. Ha n és n - a páros, a grafikon Euler. Ha n = n. akkor a gráf Hamilton.
Súlyozott gráf egy gráfot, melynek csúcsai és (vagy) van rendelve a bordák „mérleg” - általában néhány számot. Példa a súlyozott gráf - közlekedési hálózat, amelyben az élek súlyokkal, ami azt jelenti, a költségek az áruszállítás széle mentén és kapacitások az íveket. Példa súlyozott alábbi grafikonon.
A fa egy összefüggő gráf nélküli ciklusok (lásd az alábbi ábrát). Bármely két pont között csak egy fa útvonalon.
Q Az élek száma a grafikon az aránya
ahol n - a csúcsok száma a fa.
Az előírt arányát fejezi ki a kritikus érték az a fa éleit, mintha ehhez hozzátesszük, hogy a fa még él, a hurok jön létre, és ha uberom egyik szélét, a grafikon-tree van osztva két összetevője van. A grafikon áll egy fa alkatrész, az úgynevezett erdőben.
A grafikonok formájában, különösen abban a formában a fák, hogy egy csomó matematikai modellek. amely szintén megtalálható a honlapunkon.
Az egész egység „Graph Theory”