Studijní materiály

Zpět

Hromadně přidat materiály

Tahák

DM - Diskrétní matematika

Hodnocení materiálu:

Zjednodušená ukázka:

Stáhnout celý tento materiál

Stupeň uzlu – je počet hran se kterými uzel inciduje; značí se /x/. Uzel x je izolovaný jestliže /X/ =0. Vlastnost 1. součet
všech uzlů=dvojnásobku počtu hran vlastnost 2počet uzlů lichého stupně je vždy sudé číslo.Graf G'(U'H')Je podgraf
grafu G=(U,H) jestliže U'(U a H'(H, přičemž H'obsahuje hrany spojující pouze uzly z U'. Podgraf je část Grafu který
vznikne tak že vybereme některé hrany (podmnožinu hran) a k nim všechny uzly, které s těmito hranami Iniciují.Podgraf
je faktor jestliže má stejnou množinu uzlů. Graf je souvislí existuje-li mezi každými jeho uzly alespoň jeden sled, obrazně
řečeno graf je souvislý lze-li jej zavěsit jako celek.Komponenta – je maximální souvislý podgraf grafu,který obsahuje
uzel u. Jeli graf souvislý pak jsou komponenty všech uzlů rovny a rovnají se grafu. Pravidelný graf: graf je pravidelný
graf stupně n, mají-li všechny jeho uzly týž stupeň n.Pravidelný graf se stručně nazývá kružnice. Strom – je souvislý
graf, který neobsahuje žádnou kružnici jako podgraf. Vlastnost1-ve stromu existuje právě jeden sled (který je cestou) z
jednoho uzlu do druhého.vlastnost 2.vynechání lib.hrany ze stromu způsobí že se ze stromu stane nesouvislý graf. vlast3
ves tromu existují alespoň dva různé uzly stupně 1. vlast.4 počet hran je o jednu menší než počet uzlů. V každém souvislém
grafu existuje jeho faktor , který je strom; nazývá se kostra. Graf je planární lze-li jej nakreslit v rovině tak, že žádné dvě
hrany se neprotínají mezi uzly. V opač.případě je neplenární. V1: h ( 3 u-6 V2: h ( 2 u – 4. Chromatické číslo grafu:
je minimální k k obarvení grafu k-barvy. Vlastn.1 je li k-chromatický je i k+1 chromatický. Vlastn.2 chrom č.1 mají
pouze grafy složené z idol.uzlů vlatn3. graf má chrom.č2 právě když neobsahuje kružnici liché délky. Stromy mají chrom
č.2. chrom.č.planárního grafu není větší než.4
Stupeň uzlu – je počet hran se kterými uzel inciduje; značí se /x/. Uzel x je izolovaný jestliže /X/ =0. Vlastnost 1. součet
všech uzlů=dvojnásobku počtu hran vlastnost 2počet uzlů lichého stupně je vždy sudé číslo.Graf G'(U'H')Je podgraf
grafu G=(U,H) jestliže U'(U a H'(H, přičemž H'obsahuje hrany spojující pouze uzly z U'. Podgraf je část Grafu který
vznikne tak že vybereme některé hrany (podmnožinu hran) a k nim všechny uzly, které s těmito hranami Iniciují.Podgraf
je faktor jestliže má stejnou množinu uzlů. Graf je souvislí existuje-li mezi každými jeho uzly alespoň jeden sled, obrazně
řečeno graf je sou

Stáhnout celý tento materiál

1 2 3

Další

Vloženo: 22.04.2009

Velikost: 43,00 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.

Mohlo by tě zajímat:

Skupina předmětu DM - Diskrétní matematika
Reference vyučujících předmětu DM - Diskrétní matematika

Podobné materiály