Zk. 1.6.2009 - Kratochvil

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.

Zk. 1.6.2009 - Kratochvil

Příspěvekod Marex » 1. 6. 2009 21:00

Bylo 6 prikladu:

1) Urcete pocet koster tohoto grafu:
Obrázek
2) Urcete vytvorujici funkci pro posloupnost (2, 1, 3, 2, 4, 3, 5, 4, ...)
3) Rozhodnete, pro ktera prirozena cisla m, n obsahuje uplny bipartitni graf Km,n Hamiltonovskou kruznici
4) Najdete nejvetsi parovani v nasledujicim grafu a zduvodnete, proc je nalezene parovani nejvetsi:
Obrázek
5) Dokazte, ze kazdy vrcholove 2-souvisly graf o n vrcholech ma alespon n koster. Popiste vsechny vrcholove 2-souvisle grafy o n vrcholech, ktere maji prave n koster.
6) Necht n >= 3 je prirozene cislo. Necht A1, A2, ..., An je system n ruznych mnozin velikosti n-2. Dokazte, ze tento system ma system ruznych reprezentantu.

Bodovani:
Priklady 1-4 za 6 bodu.
Priklady 5-6 za 8 bodu.
Celkovy mozny zisk je 40 bodu.

Hodnoceni:
40-34: 1
31-28: 2
26-19: 3
15-14: ustni
(mezery v bodovani znamenaji, ze takovy pocet bodu nikdo nemel)

(Je to prepis z fotky, kreslit neumim, melo by to byt spravne, patches are welcome)
Marex
Matfyz(ák|ačka) level I
 
Příspěvky: 5
Registrován: 7. 6. 2008 12:59
Typ studia: Informatika Bc.
Login do SIS: vasum7am

Re: Zk. 1.6.2009 - Kratochvil

Příspěvekod Sranda » 11. 6. 2009 23:02

Nekdo ma reseni 6. prikladu.

Hallova podminka rika, ze
pro kazde L z {1...n}, |L| <= |U Ai|

ale
* |U Ai| = n-2
* kdyz bereme L = {1,2,3,..n} => |L| = n => n>n-2 => A1,A2,...,An nema SRR.

Je to spravne nebo jsem mimo.
Sranda
 

Re: Zk. 1.6.2009 - Kratochvil

Příspěvekod Návštěvník » 11. 6. 2009 23:59

Myslim si ze |Ai|=n-2 a sjednoceni Ai muze byt vice nez n.
indukci podle L plati az do n-1

pro |L|=n
SPOREM: |U Ai|<=n-1 , z toho plyne, ze system ma maximalne n-1 ruznych prvku. Kazdy mnozina obsahuje n-2 prvku.
odtud vime ze (n-2) z (n-1) = n-1. (pocet ruzne mnoziny) SPOR. Ale system ma n ruzne mnoziny.
Návštěvník
 


Zpět na DMI011 Kombinatorika a grafy I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků