Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Graf teorisi, çizge teorisi veya çizit teorisi (İngilizce: graph theory), grafları inceleyen matematik dalıdır. Graf, düğümler ve bu düğümleri birbirine bağlayan kenarlardan oluşan bir tür ağ yapısıdır. Bir graf, çizge veya çizit, düğümlerden (köşeler) ve bu düğümleri birbirine bağlayan kenarlardan (yaylardan, bağıntılardan) oluşur.
Temeli 1736'da Leonhard Euler tarafından atılmıştır.
Graf teorisi üzerinde yapılan çalışmalar, Petri ağları gibi birçok yeni kavramın geliştirilmesine imkân sağlamıştır.
Teorinin tarihi
Leonhard Euler tarafından, 1736 yılında, Königsberg'in yedi köprüsü (Almanca: Die Sieben Brücken von Königsberg) adında günümüzde hâlâ popülerliğini koruyan bir problem ile ilgili olarak yazılan bir makale, graf teorisinin kesin başlangıç tarihidir.
Matematiksel tanımı
Bir G grafı iki küme ile ifade edilir: G = (D, K). Bu ifadede D düğümler kümesi, K ise (düğümler ile ilişkili) kenarlar kümesi olarak ifade edilir.
- Eğer düğümleri birbirine bağlayan kenarlar için giriş ve çıkış yönleri belirli ise bu kenarlara yönlü kenarlar denir.
- Eğer bir düğümden çıkan ve yine aynı düğüme giren bir kenar varsa (mesela A'dan çıkıp A'ya yeniden giren bir kenar), bu bir döngü (İngilizce: loop) olarak ifade edilir.
- Eğer bir düğümden bir başka düğüme giden aynı yöne sahip veya yönsüz iki adet kenar varsa bu kenarlara paralel kenarlar denir.
Sağdaki yönsüz, örnek graf için küme gösterimi aşağıdaki şekilde yapılır.
D = {A, B, C, D}
K = {(A, D), (D, A), (A, B), (A, C), (C, B), (C, D)}
G = (D, K)
Bu örnekte A ve D düğümleri iki adet paralel kenar içerir.
Graf tipleri
| Graf tipi | Kenar tipi | Çoklu kenara izin | Döngüye izin? |
|---|---|---|---|
| Basit graf | Yönsüz | Hayır | Hayır |
| Çoklu graf | Yönsüz | Evet | Hayır |
| Pseudo (sahte) graf | Yönsüz | Evet | Evet |
| Yönlü graf | Yönlü | Hayır | Evet |
| Yönlü çoklu graf | Yönlü | Evet | Evet |
Tanımlar ve örnekler
Yol haritasıyla haritada belirtilen yollarla bir beldeden diğer bir beldeye nasıl gidileceğine karar verilir. Sonuç olarak bu durumda nesnelerin iki farklı kümesi ile ilgilenilmektedir: Beldeler ve yollar. Daha önce gördüğümüz gibi böyle nesnelerin kümeleri bir bağıntı tanımlamak için kullanılabilir. Eğer V kümesi ile beldeler kümesini ve E kümesi ile de yollar kümesini gösterirsek, V kümesi üzerinde yalnız E'deki yolları kullanarak a beldesinden (noktasından) b noktasına seyahat edilebiliyorsa aβb yazarak, bir β bağıntısı tanımlanabilir. Eğer E'deki yollar gidiş-geliş yolları ise bβa da gerçeklenir. Eğer inceleme altındaki bütün yollar gidiş-gelişli yollar ise bu bağıntı simetriktir. Bir bağıntıyı tanımlamanın bir yolu, onun elemanlarını sıralı çiftler olarak listeleyerek vermektir. Bunun, aşağıdaki şekilde gösterildiği gibi çizgiler kullanarak yapılması daha uygundur.
Ayrıca bakınız
Kaynakça
- ^ (İngilizce) Biggs, N.; Lloyd, E. and Wilson, R. (1986), Graph Theory, 1736-1936, Oxford University Press.
Dış bağlantılar
- Graf teorisi
 | Matematik ile ilgili bu madde seviyesindedir. Madde içeriğini genişleterek Vikipedi'ye katkı sağlayabilirsiniz. |
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Graf teorisi cizge teorisi veya cizit teorisi Ingilizce graph theory graflari inceleyen matematik dalidir Graf dugumler ve bu dugumleri birbirine baglayan kenarlardan olusan bir tur ag yapisidir Bir graf cizge veya cizit dugumlerden koseler ve bu dugumleri birbirine baglayan kenarlardan yaylardan bagintilardan olusur Ornek bir cizge Temeli 1736 da Leonhard Euler tarafindan atilmistir Graf teorisi uzerinde yapilan calismalar Petri aglari gibi bircok yeni kavramin gelistirilmesine imkan saglamistir Teorinin tarihiKonigsberg kopruleri sorunu Leonhard Euler tarafindan 1736 yilinda Konigsberg in yedi koprusu Almanca Die Sieben Brucken von Konigsberg adinda gunumuzde hala populerligini koruyan bir problem ile ilgili olarak yazilan bir makale graf teorisinin kesin baslangic tarihidir Matematiksel tanimiSolda matematiksel ifadesi bulunan ornek G grafi Bir G grafi iki kume ile ifade edilir G D K Bu ifadede D dugumler kumesi K ise dugumler ile iliskili kenarlar kumesi olarak ifade edilir Eger dugumleri birbirine baglayan kenarlar icin giris ve cikis yonleri belirli ise bu kenarlara yonlu kenarlar denir Eger bir dugumden cikan ve yine ayni dugume giren bir kenar varsa mesela A dan cikip A ya yeniden giren bir kenar bu bir dongu Ingilizce loop olarak ifade edilir Eger bir dugumden bir baska dugume giden ayni yone sahip veya yonsuz iki adet kenar varsa bu kenarlara paralel kenarlar denir Sagdaki yonsuz ornek graf icin kume gosterimi asagidaki sekilde yapilir D A B C D K A D D A A B A C C B C D G D K Bu ornekte A ve D dugumleri iki adet paralel kenar icerir Graf tipleriGraf tipi Kenar tipi Coklu kenara izin Donguye izin Basit graf Yonsuz Hayir HayirCoklu graf Yonsuz Evet HayirPseudo sahte graf Yonsuz Evet EvetYonlu graf Yonlu Hayir EvetYonlu coklu graf Yonlu Evet EvetTanimlar ve orneklerYol haritasiyla haritada belirtilen yollarla bir beldeden diger bir beldeye nasil gidilecegine karar verilir Sonuc olarak bu durumda nesnelerin iki farkli kumesi ile ilgilenilmektedir Beldeler ve yollar Daha once gordugumuz gibi boyle nesnelerin kumeleri bir baginti tanimlamak icin kullanilabilir Eger V kumesi ile beldeler kumesini ve E kumesi ile de yollar kumesini gosterirsek V kumesi uzerinde yalniz E deki yollari kullanarak a beldesinden noktasindan b noktasina seyahat edilebiliyorsa abb yazarak bir b bagintisi tanimlanabilir Eger E deki yollar gidis gelis yollari ise bba da gerceklenir Eger inceleme altindaki butun yollar gidis gelisli yollar ise bu baginti simetriktir Bir bagintiyi tanimlamanin bir yolu onun elemanlarini sirali ciftler olarak listeleyerek vermektir Bunun asagidaki sekilde gosterildigi gibi cizgiler kullanarak yapilmasi daha uygundur Ayrica bakinizArama algoritmasi En kisa yol problemi Gezgin satici problemiKaynakca Ingilizce Biggs N Lloyd E and Wilson R 1986 Graph Theory 1736 1936 Oxford University Press Dis baglantilarGraf teorisiMatematik ile ilgili bu madde taslak seviyesindedir Madde icerigini genisleterek Vikipedi ye katki saglayabilirsiniz