GoBack
Hamilton-körök és DNS molekulák Tengely Szabolcs 2005. november 4
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 1
Gráfok ❖ Gráfok
●
G = (V, E) egyszeru˝ gráf, ha V egy véges halmaz és E ⊆ V2 ,
❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
V elemei a G gráf csúcsai,
●
E elemei a G gráf élei,
1 halmazok ❖ Sn
●
(a, b)-út: a = x0 , e1 , x1 , . . . , en , xn = b sorozat, ahol xi 6= xj , i 6= j esetén,
●
kör: a = x0 , e1 , x1 , . . . , en , x0 = a sorozat, ahol az x0 , x1 , . . . , xn−1 csúcsok és az e1 , e2 , . . . , en élek ˝ páronként különbözoek,
●
Hamilton-út: olyan G-beli út, amely G minden pontját tartalmazza,
●
Hamilton-kör: olyan G-beli kör, amely G minden pontját tartalmazza.
❖ Példa ❖ Nehéz dió ❖ DNS molekulák
1 ❖ Sn
6= ∅
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 2
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
8
1
9
2
10
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
●
0
❖ Példa ❖ Nehéz dió
4
5
csúcsok halmaza: {0, 1, . . . , 11}
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
8
1
9
2
10
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4 8
1
csúcsok halmaza: {0, 1, . . . , 11}
●
élek halmaza: {(0, 1), (0, 2), . . . , (10, 11)}
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
9
2
10
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4
1 ❖ Sn 1 ❖ Sn
8
1
csúcsok halmaza: {0, 1, . . . , 11}
●
élek halmaza: {(0, 1), (0, 2), . . . , (10, 11)}
●
(0, 11)-út: 0 − 4 − 1 − 6 − 11
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
9
2
10
halmazok 6= ∅
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4
1 ❖ Sn 1 ❖ Sn
8
1
csúcsok halmaza: {0, 1, . . . , 11}
●
élek halmaza: {(0, 1), (0, 2), . . . , (10, 11)}
●
(0, 11)-út: 0 − 4 − 1 − 6 − 11
●
kör: 0 − 1 − 3 − 2 − 0
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
9
2
10
halmazok 6= ∅
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4
1 ❖ Sn 1 ❖ Sn
8
1
csúcsok halmaza: {0, 1, . . . , 11}
●
élek halmaza: {(0, 1), (0, 2), . . . , (10, 11)}
●
(0, 11)-út: 0 − 4 − 1 − 6 − 11
●
kör: 0 − 1 − 3 − 2 − 0
●
Hamilton-út: 0 − 4 − 1 − 6 − 3 − 7 − 2 − 5 − 8 − 9 − 11 − 10
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
9
2
10
halmazok 6= ∅
❖ Gn alkalmazása
11
❖
6
7 3
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Példa ❖ Gráfok
0
❖ Példa ❖ Nehéz dió
4
1 ❖ Sn 1 ❖ Sn
8
1
csúcsok halmaza: {0, 1, . . . , 11}
●
élek halmaza: {(0, 1), (0, 2), . . . , (10, 11)}
●
(0, 11)-út: 0 − 4 − 1 − 6 − 11
●
kör: 0 − 1 − 3 − 2 − 0
●
Hamilton-út: 0 − 4 − 1 − 6 − 3 − 7 − 2 − 5 − 8 − 9 − 11 − 10
●
Hamilton-kör: 8 − 10 − 11 − 9 − 4−0−1−6−3−7−2−5−8
5
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
●
9
2
10
halmazok 6= ∅
❖ Gn alkalmazása
11
❖
6
7 3
Tétel.(Dirac, 1952) Legyen G n-pontú egyszeru˝ gráf, ahol n ≥ 3. Ha G-ben minden pont foka legalább n/2, akkor G-ben van Hamilton-kör.
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 3
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal.
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben,
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben, 2. minden út esetében vizsgáljuk meg:
1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben, 2. minden út esetében vizsgáljuk meg: ˝ a az út a megfelelo˝ ponttal kezdodik és a ˝ megfelelo˝ pontban végzodik, ha nem, hagyjuk ki az utat a halmazból,
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben, 2. minden út esetében vizsgáljuk meg: ˝ a az út a megfelelo˝ ponttal kezdodik és a ˝ megfelelo˝ pontban végzodik, ha nem, hagyjuk ki az utat a halmazból, b az út pontosan n csúcson megy át, ha nem, hagyjuk ki az utat a halmazból,
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben, 2. minden út esetében vizsgáljuk meg: ˝ a az út a megfelelo˝ ponttal kezdodik és a ˝ megfelelo˝ pontban végzodik, ha nem, hagyjuk ki az utat a halmazból, b az út pontosan n csúcson megy át, ha nem, hagyjuk ki az utat a halmazból, c
[email protected]
minden csúcson átmegy, ha nem, hagyjuk ki az utat a halmazból,
KöMaL Ifjúsági Ankét 2005 – slide 4
Nehéz dió ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Nem létezik effektív algoritmus Hamilton-út keresésére. Adott egy G gráf n csúccsal. 1. Generáljunk utakat G-ben, 2. minden út esetében vizsgáljuk meg: ˝ a az út a megfelelo˝ ponttal kezdodik és a ˝ megfelelo˝ pontban végzodik, ha nem, hagyjuk ki az utat a halmazból, b az út pontosan n csúcson megy át, ha nem, hagyjuk ki az utat a halmazból, c
minden csúcson átmegy, ha nem, hagyjuk ki az utat a halmazból,
3. ha maradt út, akkor létezik Hamilton-út G-ben.
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 4
DNS molekulák ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 5
DNS molekulák ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Adenine(A), Cytosine(C), Guanine(G), Thymine(T)
csak A-T, C-G kapcsolódások fordulnak elo˝
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 5
Kódolás ❖ Gráfok ❖ Példa ❖ Nehéz dió
Adleman, 1994: 7 csúcs, 14 él, 20 hosszú DNS láncok.
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 6
Kódolás ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
Adleman, 1994: 7 csúcs, 14 él, 20 hosszú DNS láncok. A mi leegyszerusített ˝ példánkban: ●
Miskolc: AAAAGGGG
●
Budapest: CCCCTTTT
●
Szeged: AGAGCTCT
●
Debrecen: GAGATCTC
KöMaL Ifjúsági Ankét 2005 – slide 6
Kódolás ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
Adleman, 1994: 7 csúcs, 14 él, 20 hosszú DNS láncok. A mi leegyszerusített ˝ példánkban: ●
Miskolc: AAAAGGGG
●
Budapest: CCCCTTTT
●
Szeged: AGAGCTCT
●
Debrecen: GAGATCTC
●
Miskolc-Budapest él: CCCCGGGG
●
Miskolc-Szeged él: CCCCTCTC
●
Miskolc-Debrecen él: CCCCCTCT KöMaL Ifjúsági Ankét 2005 – slide 6
Megoldás molekulák ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
Miskolcról kiindulva keresünk Hamilton-kört, minden kódoló molekula hossza 8, így 40 hosszú molekulákat keresünk.
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 7
Megoldás molekulák ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn
Miskolcról kiindulva keresünk Hamilton-kört, minden kódoló molekula hossza 8, így 40 hosszú molekulákat keresünk. Egy megoldást meghatározó molekula: AAAA
CCCC GGGG
CTCT GAGA
AGAG TCTC
TTTT AAAA
CCCC GGGG
CTCT GAGA
AGAG TCTC
TTTT AAAA
GGGG
Miskolc-Debrecen-Budapest-Szeged-Miskolc.
1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 7
Megoldás molekulák ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn
Miskolcról kiindulva keresünk Hamilton-kört, minden kódoló molekula hossza 8, így 40 hosszú molekulákat keresünk. Egy megoldást meghatározó molekula: AAAA
CCCC GGGG
CTCT GAGA
AGAG TCTC
TTTT AAAA
CCCC GGGG
CTCT GAGA
AGAG TCTC
TTTT AAAA
GGGG
Miskolc-Debrecen-Budapest-Szeged-Miskolc.
1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Nem megoldás, de megfelelo˝ hosszúságú: AAAA
CCCC GGGG
CTCT GAGA
AGAG TCTC
GGGG CCCC
AAAA TTTT
TCTC AGAG
GAGA CTCT
TTTT AAAA
GGGG
Miskolc-Debrecen-Miskolc-Debrecen-Miskolc
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 7
Hossz - megoldhatóság ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
Adlemannak meg kellett határoznia a sorozatokat, hogy eldöntse a Hamilton-út létezésének kérdését. ˝ (Idoigényes) Viszont pozitív válasz esetén konstruktív eljárás!
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 8
Hossz - megoldhatóság ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
Adlemannak meg kellett határoznia a sorozatokat, hogy eldöntse a Hamilton-út létezésének kérdését. ˝ (Idoigényes) Viszont pozitív válasz esetén konstruktív eljárás! Frisco, Henkel, Tengely (2004): Hamilton-út létezésének eldöntése megfelelo˝ hosszúságú DNS lánc jelenléte alapján.
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 8
Hossz - megoldhatóság ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
Adlemannak meg kellett határoznia a sorozatokat, hogy eldöntse a Hamilton-út létezésének kérdését. ˝ (Idoigényes) Viszont pozitív válasz esetén konstruktív eljárás! Frisco, Henkel, Tengely (2004): Hamilton-út létezésének eldöntése megfelelo˝ hosszúságú DNS lánc jelenléte alapján.
❖
Kódolás megváltoztatása, azonos hosszúságú molekulák helyett speciálisan megválasztott DNS láncok.
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 8
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió
halmazok
Az Sn1 halmaz olyan {a1 , . . . , an } halmazokból áll, amelyekre teljesül, hogy az
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
a1 x1 + a2 x2 + . . . + an xn = a1 + a2 + . . . + an egyenletnek csak a triviális xi = 1 megoldása van, ahol xi ≥ 0 egész.
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 9
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió
halmazok
Az Sn1 halmaz olyan {a1 , . . . , an } halmazokból áll, amelyekre teljesül, hogy az
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
a1 x1 + a2 x2 + . . . + an xn = a1 + a2 + . . . + an egyenletnek csak a triviális xi = 1 megoldása van, ahol xi ≥ 0 egész.
❖ Gn alkalmazása
{4, 6, 7} ∈ S31 , mert a 4x1 + 6x2 + 7x3 = 17 egyenlet egyetlen megoldása az x1 = x2 = x3 = 1,
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 9
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió
halmazok
Az Sn1 halmaz olyan {a1 , . . . , an } halmazokból áll, amelyekre teljesül, hogy az
❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
a1 x1 + a2 x2 + . . . + an xn = a1 + a2 + . . . + an egyenletnek csak a triviális xi = 1 megoldása van, ahol xi ≥ 0 egész.
❖ Gn alkalmazása
{4, 6, 7} ∈ S31 , mert a 4x1 + 6x2 + 7x3 = 17 egyenlet egyetlen megoldása az x1 = x2 = x3 = 1,
❖
{3, 5, 7} ∈ / S31 , mert x1 = 0, x2 = 3, x3 = 0 is megoldás.
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 9
1 Sn ❖ Gráfok ❖ Példa
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás.
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }.
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }. ●
G1 = {1}
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }. ●
G1 = {1}
●
G2 = {2, 3}
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }. ●
G1 = {1}
●
G2 = {2, 3}
●
G3 = {4, 6, 7}
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }. ●
G1 = {1}
●
G2 = {2, 3}
●
G3 = {4, 6, 7}
●
G4 = {8, 12, 14, 15}
❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
1 Sn ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása
6= ∅
Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1. Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor a skatulyaelv miatt léteznek hi , hj ∈ H, hi 6= hj , amelyekre hi + hj ≡ 0 mod h. Ellentmondás. Sn Legyen Gn = i=1 {2n − 2n−i }. ●
G1 = {1}
●
G2 = {2, 3}
●
G3 = {4, 6, 7}
●
G4 = {8, 12, 14, 15}
❖
Tétel. Minden pozitív egész n-re Gn ∈ Sn1 .
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 10
Gn alkalmazása ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság
Az egyszeru˝ Budapest-Debrecen-Miskolc-Szeged példánkban Debrecen-Szeged Hamilton-út létezésének kérdése esetén használhatjuk Gn elemeit, mint a csúcsok kódjait:
1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 11
Gn alkalmazása ❖ Gráfok ❖ Példa ❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
Az egyszeru˝ Budapest-Debrecen-Miskolc-Szeged példánkban Debrecen-Szeged Hamilton-út létezésének kérdése esetén használhatjuk Gn elemeit, mint a csúcsok kódjait: ●
Budapest - 8
●
Debrecen - 12
●
Miskolc - 14
●
Szeged - 15
Egy Hamilton-utat reprezentáló molekula hossza 49 lenne, ha létezik ilyen hosszú molekula, akkor létezik Debrecen-Szeged Hamilton-út és nem szükséges "dekódolni" a DNS láncokat.
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 11
❖ Gráfok ❖ Példa
Köszönöm a figyelmet!
❖ Nehéz dió ❖ DNS molekulák ❖ Kódolás ❖ Megoldás molekulák ❖ Hossz megoldhatóság 1 halmazok ❖ Sn 1 6= ∅ ❖ Sn
❖ Gn alkalmazása ❖
[email protected]
KöMaL Ifjúsági Ankét 2005 – slide 12
