-
Düzenli
-
Tam
Graf Teorisi Oyun Alanı
Graf, köşe adı verilen noktalardan ve bunları birleştiren, kenar adı verilen çizgilerden oluşur. Burada birkaç tıklamayla bir graf çizin; oyun alanı size onun nasıl bir graf olduğunu söylesin: kaç parçadan oluştuğunu, ağaç olup olmadığını, en az kaç renge ihtiyaç duyduğunu, tek çizgide çizilip çizilemeyeceğini ve daha fazlasını. Bir özelliği grafınızda görmek için ona tıklayın, bir kenarı değiştirin ve cevapların nasıl değiştiğini izleyin. Köşe eklemek için boş bir yere tıklayın. İki köşeyi bir kenarla birleştirmek için önce birine, sonra diğerine tıklayın; kenarı kaldırmak için aynısını tekrarlayın. Bir köşeyi taşımak için sürükleyin. Tıklamayı Siler konumuna getirin ve silmek istediğiniz köşeye ya da kenara tıklayın. Bir köşe seçiliyken Delete onu siler, Esc ise seçimi bırakır. Bir özelliği graf üzerinde görmek için ona tıklayın. Örnek bilinen bir grafı yükler, Rastgele graf yeni bir graf oluşturur, Düzenle köşeleri aralarında boşluk kalacak şekilde yayar, Tümleyen ise tam olarak birleşik olmayan çiftleri birleştirir. Ctrl+Z bir adımı geri alır.
Nasıl çalışır
- Köşe eklemek için boş bir yere tıklayın. Birleştirmek için bir köşeye, sonra başka birine tıklayın; kenarı kaldırmak için aynısını tekrarlayın. Bir köşeyi taşımak için sürükleyin.
- Grafın altındaki özellikleri okuyun ve birini göstermek için ona tıklayın: bir boyama, iki taraf, bir Euler yolu, bir kapsayan ağaç, en kısa döngü ya da çap.
- Petersen grafı gibi bir örnek yükleyin, rastgele bir graf oluşturun, tümleyenini alın ya da köşe ve kenarları silmek için tıklamayı Siler konumuna getirin.
Özellikler ne anlama gelir
Bir köşenin derecesi, ona bağlı kenarların sayısıdır. Her köşeden kenarlar boyunca diğer her köşeye ulaşılabiliyorsa graf bağlantılıdır; bağlantılıysa ve hiç döngüsü yoksa bir ağaçtır. Köşeleri, her kenar bir taraftan diğerine geçecek şekilde iki tarafa ayrılabiliyorsa graf iki parçalıdır; bu da tam olarak tek uzunlukta hiç döngüsü olmadığında gerçekleşir. Kromatik sayı, komşu köşelere farklı renkler vermek için gereken en az renk sayısıdır. En kısa döngünün uzunluğuna grafın çevresi (girth) denir; çap ise iki köşe arasındaki, kenar sayısıyla ölçülen en büyük uzaklıktır.
Tek çizgide çizmek
Bir Euler yolu her kenarı tam olarak bir kez kullanır. Leonhard Euler 1736'da Königsberg'in yedi köprüsü üzerinden buna neyin engel olduğunu gördü: bir yol bir köşeden her geçtiğinde o köşenin iki kenarını kullanır. Dolayısıyla ya tüm dereceler çifttir ve yol başladığı yerde bitebilir ya da tam olarak iki derece tektir ve yol bunlardan birinden diğerine gitmek zorundadır. Carl Hierholzer daha sonra, tüm kenarlar tek parçadaysa bu koşulun yeterli de olduğunu kanıtladı. Ev örneğini yükleyin ve çizginin nereden başlaması gerektiğini bulun.
Sık sorulan sorular
Graf teorisinde graf nedir?
Köşe ya da düğüm adı verilen noktalardan ve bunların bazı çiftleri arasındaki, kenar adı verilen çizgilerden oluşan bir yapıdır. Bir fonksiyonun grafiği değildir: yalnızca neyin neye bağlı olduğunu anlatır. Yol haritaları, sosyal ağlar, moleküller ve bilgisayar ağları birer graftır.
Kromatik sayı nasıl hesaplanır?
Oyun alanı grafı önce bir renkle, sonra iki, sonra üç renkle ve böyle devam ederek boyamayı dener; her sayı için önemli olan tüm olasılıkları tarar ve sıradaki olarak her zaman komşuları en çok farklı rengi kullanan köşeyi boyar. İşe yarayan ilk sayı kromatik sayıdır. Burada çizebileceğiniz graflar için bu en fazla bir an sürer; çok zor bir grafta arama erken durur ve değer bir üst sınır olarak gösterilir.
Bir grafta ne zaman Euler yolu vardır?
Tüm kenarları tek bir parçadaysa ve en fazla iki köşenin derecesi tekse. Tek dereceli köşe yoksa, başladığı yerde biten bir Euler devresi vardır; iki tane varsa her Euler yolu bunlardan birinde başlar ve diğerinde biter. Tek dereceli köşelerin sayısı her zaman çifttir, bu yüzden asla tam olarak bir olamaz.
Bir grafın tümleyeni nedir?
Aynı köşeler üzerinde kurulan ve kenarları tam olarak daha önce birleşik olmayan çiftlerden oluşan graftır. Tümleyenin tümleyeni, başladığınız grafın kendisidir. Örneğin Petersen grafının tümleyeni 6-düzenlidir, çünkü her köşe diğer 9 köşenin 3'üne bağlıydı.
Petersen grafı neden ünlüdür?
10 köşesi ve 15 kenarı olan, pek çok iyimser tahmine karşı örnek oluşturan küçük bir graftır. Her köşenin derecesi 3'tür, en kısa döngüsünün uzunluğu 5'tir, herhangi iki köşe arasında en fazla 2 kenar vardır ve kenarlar kesişmeden çizilemez. Oyun alanı onunla açılır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git