Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

FURA VONALZÓK

No description
by

András Ajtay

on 12 October 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of FURA VONALZÓK

Elegáns Gráf
Ami még kimaradt
1944-ben Simon Sidon ötlete által Erdős Pál és Turán Pál arra jött rá hogy a Sidon sorozatoknak köze lehet a Golomb vonalzókhoz.
Fura vonalzók
Vágjunk bele!
Solomon Golomb
Matematikus
Róla neveztek el ezeket a vonalzokat
John Hopkinson és Harvard egy.
IEEE Hamming-medal
polyomino: 1x1-es negyzetek
Hiányos vonalzók

5 beosztás, 11-ig mér:
itt a 6 hiányzik

itt a 10 hiányzik


izomorf
: egyenértékű vonalzók
0, 2, 7, 8, 11 izomorf 0, 3, 4, 9, 11

Hasonlóságok, megfigyelések
Eltérő vonalzó, ugyanazok a különbségek
Távolságok 1-6: 4 beosztás min.
Tavolságok 1-10: 6 beosztás min.
Fentiekkel 1-7-ig lehet mérni
6 beosztás -> 1-7-ig mindent lemér, 1-8-ig nem biztos
az 1. es 3. vonalzó: 1-17-ig mér,
kihagyva: 14 és 15-ös táv
0, 1, 4, 10, 12, 17
0, 1, 4, 10, 15, 17
0, 1, 8, 11, 13, 17
0, 1, 8, 12, 14, 17
Vannak olyan vonalzók, amelyek nem izoformok, mégis ugyanazokat a távolságokat nélkülözik
Fura vonalzók Gráfok
Sidon sorozat
Egy sorozat Sidon sorozat, ha a páronkénti összegek különbözőek.
Golomb vonalzók létrehozása
Ez a módszer minden páratlan p prímre működika következésképpen:

Minden egyes k egész számra 0 és p-1 között számoljuk ki a következőt:
2pk + (k^2 p-vel vett osztási maradéka)
Példa:
p=5
k=0; 2(5)0+0=0
k=1; 2(5)1+1=11
k=2; 2(5)2+4=24
k=3; 2(5)3+4=34
k=4; 2(5)4+1=41
~Gráf
A gráf egy diagram, ami
pontokból

és

vonalakból
áll.

A pontok a

csúcsok
és a vonalak az
élek
.

Teljes gráf
ban bármely két csúcs össze van kötve egy éllel.
Fokszáma
a gráfban, az élek száma, ami bele fut abba a csúcsba.

Egy “n” csúccsal rendelkező
teljes
gráfban minden csúcs fokszáma (n-1).
Mivel n csúcs van és minden élnek pontosan 2 végpontja van, ezért az élek száma egy
teljes
gráfban
n(n-1)/2.
A legtöbb különböző távolság
k jelölés
távolság 2 jelölés által van meghatározva
hány féle képpen választhatunk ki 2 jelölést k közül
k(k-1)/2
n-1 (1 és n-1 ekvivalens)
n-2 jobbról balra: 1-0=2-1 balról jobbra jó

Oldalról lehet csak felmérni a távolságokat.

n-3

=(n-2)-1
n-4 balról jobbra: (n-2)-(n-4)=n-(n-2)
jobbról balra jó
n-5 balról jobbra 4-1=(n-2)-(n-5)
jobbról balra 5-4=1-0
A három lehetséges tökéletes Golomb vonalzó:
0 1
0 1 3
0 1 4 6
Ennyi különböző távolságot mérhetünk le egy "n" jelet tartalmazó vonalzóval.
csúcsok
: 0-X-ig megszámozva (kihagyással is lehetetséges)
élek
: csúcsok különbségének abszolút értéke
az éleken szereplő értékek különbözőek

Vonalzók
Áltlános vonalzók:
sok fölösleges beosztás
egy távolság többször is megmérhető
Golomb vonalzók:
minden távolság csak egyszer mérhető le 0-k-ig
Vonalzó típusok
teljes vonalzó:
1-től a végéig (L) minden
tökéletes vonalzó:
mindent lemér és kevesebből nem lehet


Golomb vonalzó:
minden távolság különböző
tökéletes Golomb vonalzó:
minden távolságot lemér és mind különböző
0, 1, 2, 3, 4, 5
0, 1, 3, 4, 5
0, 1, 3, 5
0, 1, 2, 3, 4, 5, 6
0, 1, 3, 4, 5, 6
0, 1, 4, 5, 6
0, 1, 4, 6
Vonalzók II.
Sejtések és új módszerek
Sejtések
Gerhard Ringel: Ha adott egy meghatározott F fa t éllel, akkor szét lehet bontani a 2t+1 csúsú teljes gráfot F 2t+1 izomorf másolatára.
Ringel és Anton Kötzig: Minden fának van elegáns megjelölése.
Ezekből következik:
Tétel (Alexander Rosa):
Ha F egy fa t éllel, amit meg lehet elegánsan jelölni, akkor a teljes gráfot 2t+1 csúccsal szét lehet bontani a F 2t+1 másolatára.
Új módszerek
Bizonyítás
Indirekt tegyük fel, hogy S egy véges Sidon sorozat és nem hoz létre Golomb vonalzót.
a-b=c-d a+d=c+a
de ez ellentmond a definíciónak, hogy a páronkénti összegek különbözőek,
tehát S-nek muszáj egy Golomb vonalzót létrehoznia.
Jelöljük meg nem negatív egész számokkal a teljes gráf csúcsait, 0-tól kezdve.
Aztán megjelöljük a gráf éleit a két végpontjánál lévő egészek különbségének abszolút értékével.
vonalzó
gráf
fa
:
körmentes gráf
n csúcshoz n-1 él
hernyó
:



Minden hernyónak van elegáns színezése.
Több vonalzó
Miért ne használhatnánk például két vonalzót?
0, 8, 9, 12
0, 6, 11, 13
Bejelölések
Mért távolságok
1, 3, 4, 8, 9, 12
2, 5, 6, 7, 11, 13
Ez a kettő 12 távolságot mér 13-ig, és csak a 10 marad ki.

Fontos, hogy ha több vonalzót használunk, akkor egyik se végződhet ugyanarra a számra.
Él elhagyása gráfból
Ahogy bizonyíttuk is, nem lehet az 5 csúcsú teljes gráfot elegensán megjelölni.

De mi lenne, he elhagynánk egy élt?
Kiderül, hogy így már lehetséges!
A furavonalzókat sok helyen
használhatóak:
diffrakciós mintázatok, amelyek a röntgen diffrakciós vizsgálatok eredményeként keletkeznek a kristályok szerkezetét vizsgálva
konvolúciós kódok
radar és szonár
Costas arrays
mintázat illesztés és az információ visszakeresése
kódok fotodetektorok szinkronizálására
radar pulzus kódok
rakéta irányitó kódok
radio frekvencia adás sávok
radio csillagászat
Köszönjük a figyelmet!
Készítette:
9.c:
Siemelink Hanna
Umann Andor
Molnár Roland
Ajtay András
10.b:
Sturovics Dóra
Bihari Amanda
Balogh Ervin
Forrás:
és még segített:

15.c:
Palincza Richárd
Joseph Malkevitch
(York College):
Weird Rulers

http://www.ams.org/samplings/feature-column/fc-2012-01
Csonka Dorottya


Következmény:
Nincs 4-nél több jelöléssel tökéletes Golomb vonalzó!

Felkészítő tanár:
Full transcript