Fák, jellemzésük
Tree - egy csatlakoztatott aciklikus gráf (azaz grafikon nélkül ciklusok pontosan egy út van bármely pontpár) [1].
Orientált (irányított) fa - egy aciklikus irányított gráf (irányított gráf nélkül ciklus), amelyben csak egy csomópont nulla fokos megközelítés (benne nem vezet az ív), és az összes többi csúcsának foka hívás 1 (vezetnek pontosan egy ív ). Tetejét egy nulla fokos megközelítés az úgynevezett gyökér a fa, a tetejét nulla fokos eredményét (amelyek egyike sem ív árad) nevű végpont vagy a levélre. [2]
Wood nincs több élek és hurkok.
Bármilyen fa n csúcsú tartalmaz n - 1 borda. Ezen túlmenően, a végső csatlakoztatott gráf egy fa, ha, és csak akkor, ha a B - P = 1, ahol B - a csúcsok száma, P - élek számát a grafikon.
Gráf egy fa akkor és csak akkor bármely két különálló csúcs ez lehet csatlakozni csak elemi módon.
Bármilyen fa egyértelműen meghatározzák a távolságok (alsó lánchosszúságú) közötti végén (foka 1) csúcsok.
Bármilyen fa egy páros gráf. Bármilyen fa tartalmazó megszámlálható csúcsok száma egy sík grafikon.
Bármely három csúcsa egy fa, a pályák között pár csúcsai pontosan egy közös csúcsa.
Egy feszítőfának (váz) - egy részgráfját egy grafikon, amely az összes a csúcsait, és egy fa. Élek a grafikon nem része a csontváz, az úgynevezett egy grafikon tekintetében a mag akkordokat.
Boole-algebra, logikai rács - részben rendezett halmaz speciális formája; elosztó rács, amelynek a legnagyobb tag 1 - egyik Boole algebra, a legkisebb elem 0 - nulla Boole algebra, és amely csak túlmenően minden egyes eleme az X - elem (nem x)
Komplett grafikonok. komplementer gráf. Komplett részgráfok. Ramsey tétele.
Teljes Count - egyszerű gráf, ahol minden egyes különböző pár szomszédos csúcsok. A teljes gráf n pontú n (n - 1) / 2
A gráfelmélet komplement vagy inverz egy G gráf egy grafikon, H, amelynek ugyanaz csúcshalmaza G, de amelyben két nem egybeeső csúcsok szomszédos, ha, és csak akkor, ha azok nem szomszédos G. Annak érdekében, hogy megtalálják a fordított grafikon, hozzáadjuk a gróf befejezni, és távolítsa el az összes éleket, amelyek már korábban.
Klikk (teljes részgráfját) - egy részhalmazát a csúcsok, minden két amelyek össze vannak kötve egy éllel a grafikon.
Hagyja, hogy a megadott számok a1, a2. egy. Ekkor létezik egy sor R, ami nem számít, hogyan festett a széleit a teljes gráf R felsők n színben létezik egy teljes részgráf 1. szín a1 tetejét vagy teljes részgráf 2. szín a2 felsők ... teljes részgráf n-edik szín egy tetejét.
Boole-gyűrű nevezett gyűrű, amelyben minden elem idempotens (kommutativitás, a önálló biztonsági egység jelenlétében, vagy zérusosztó nem szükséges). Egy érdekes tulajdonsága logikai gyűrű az, hogy
különösen a
azaz logikai gyűrű mindig kommutatív.
Páros gráfok, a szükséges és elégséges feltétele létezését.
Páros gráf vagy kétrétegű grafén - amely egy matematikai kifejezés az elmélet a grafikonok jelezve a gráfot, melynek csúcshalmaza feloszthatjuk két részre úgy, hogy minden éle a grafikon összeköti néhány csúcs az egyik oldalán egyfajta csúcsra a másik része, azaz, nincs borda összekötő két csúcsot ugyanezen részét.
A gráf páros akkor és csak akkor nem tartalmaz ciklust páratlan hosszúságú. Ezért páros gráf nem tartalmazhat több, mint 2 klikk.
Egy gráf páros, ha, és csak akkor, ha 2-színezhető (azaz a kromatikus száma egyenlő két)
A grafikon van osztva pár színű csúcsok, ha és csak akkor, ha bármelyik k elemet részesedés jár legalább k más elemek (Hall-tétel).
Páros gráf, amely mind a több, mint 2-pontú nem planáris.
Rács. Group. Egyoperandusú algebra.
