GoBackHamilton-körök és DNS molekulák
Tengely Szabolcs
2005. november 4tengely@math.klte.hu

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 élekpáronként különbözőek,●

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
6= ∅
❖ Sn

❖ Gn alkalmazása❖

tengely@math.klte.hu

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

tengely@math.klte.hu

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

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 3

Példa❖ Gráfok

0❖ Példa❖ Nehéz dió

4
81

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

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 3

Példa❖ Gráfok

0❖ Példa❖ Nehéz dió

4
8

1

9

2

10

1
halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása

csúcsok halmaza:{0, 1, . . . , 11}●élek halmaza:{(0, 1), (0, 2), . . . , (10, 11)}●(0, 11)-út: 0 − 4 − 1 − 6 − 115

❖ DNS molekulák❖ Kódolás❖ Megoldás
molekulák❖ Hossz megoldhatóság

●

11

❖

6

7
3

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 3

Példa❖ Gráfok

0❖ Példa❖ Nehéz dió

4
8

1

9

2

10

1
halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása

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

●

11

❖

6

7
3

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 3

Példa❖ Gráfok

0❖ Példa❖ Nehéz dió

4
8

1

9

2

10

1
halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása

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 − 105

❖ DNS molekulák❖ Kódolás❖ Megoldás
molekulák❖ Hossz megoldhatóság

●

11

❖

6

7
3

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 3

Példa❖ Gráfok

0❖ Példa❖ Nehéz dió

4
8

1

9

2

10

1
halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása

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

●

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.
tengely@math.klte.hu

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❖

tengely@math.klte.hu

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,1halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása❖

tengely@math.klte.hu

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❖

tengely@math.klte.hu

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❖

tengely@math.klte.hu

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 kezdődik és amegfelelő pontban végződik, 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 kezdődik és amegfelelő pontban végződik, 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,

tengely@math.klte.hu

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 kezdődik és amegfelelő pontban végződik, 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,ctengely@math.klte.hu

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 kezdődik és amegfelelő pontban végződik, 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,cminden csúcson átmegy, ha nem, hagyjuk ki
az utat a halmazból,

3. ha maradt út, akkor létezik Hamilton-út G-ben.
tengely@math.klte.hu

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❖

tengely@math.klte.hu

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̋tengely@math.klte.hu

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❖

tengely@math.klte.hu

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❖

tengely@math.klte.hu

Adleman, 1994: 7 csúcs, 14 él, 20
hosszú DNS láncok. A mi leegyszerűsí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❖

tengely@math.klte.hu

Adleman, 1994: 7 csúcs, 14 él, 20
hosszú DNS láncok. A mi leegyszerűsített példánkban:●

Miskolc: AAAAGGGG●

Budapest: CCCCTTTT●

Szeged: AGAGCTCT●

Debrecen: GAGATCTC●

Miskolc-Budapest:
CCCCGGGG●

Miskolc-Szeged:
CCCCTCTC●

Miskolc-Debrecen:
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❖

tengely@math.klte.hu

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❖

tengely@math.klte.hu

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

tengely@math.klte.hu

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.
(Időigényes)
Viszont pozitív válasz esetén konstruktív eljárás!

1
halmazok
❖ Sn
1
6= ∅
❖ Sn

❖ Gn alkalmazása❖

tengely@math.klte.hu

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.
(Időigé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.

❖tengely@math.klte.hu

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.
(Időigé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.

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 8

1
Sn halmazok❖ Gráfok❖ Példa❖ Nehéz dió

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 + . . . + anegyenletnek csak a triviális xi = 1 megoldása van, aholxi ≥ 0 egész.

❖ Gn alkalmazása❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 9

1
Sn halmazok❖ Gráfok❖ Példa❖ Nehéz dió

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 + . . . + anegyenletnek csak a triviális xi = 1 megoldása van, aholxi ≥ 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,❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 9

1
Sn halmazok❖ Gráfok❖ Példa❖ Nehéz dió

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 + . . . + anegyenletnek csak a triviális xi = 1 megoldása van, aholxi ≥ 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.

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 91
Sn 6= ∅
❖ Gráfok❖ PéldaTé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❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ Gráfok❖ Példa❖ Nehéz dió❖ DNS molekulák❖ Kódolás❖ Megoldás
molekulák❖ Hossz megoldhatóság

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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}❖tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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}❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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}❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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}❖tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 10

1
Sn 6= ∅
❖ 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

Tétel. Ha h ∈ H ∈ Sn1 , akkor n ≤ h/2 + 1.
Bizonyítás. Tegyük fel, hogy n > h/2 + 1. Ekkor askatulyaelv 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 .

tengely@math.klte.hu

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❖

tengely@math.klte.hu

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.

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 11❖ Gráfok
❖ PéldaKö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❖

tengely@math.klte.hu

KöMaL Ifjúsági Ankét 2005 – slide 12