İçeriğe atla

Graf (matematik)

Altı köşeli ve yedi kenarlı bir graf.

Matematikte graf ya da çizge, nesne çiftlerinin bir anlamda "ilişkili" olduğu bir dizi nesne kümesini belirleyen bir yapıdır. Nesneler, köşeler (ayrıca düğümler veya noktalar olarak da adlandırılır) adı verilen matematiksel soyutlamalara karşılık gelir ve ilgili düğüm çiftlerinin her birine bir kenar, ayrıt (bağlantı veya çizgi olarak da adlandırılır) adı verilir.[1] Tipik olarak bir graf, kenarları için çizgiler veya eğriler ile birleştirilen, düğümler için bir nokta veya daire kümesi olarak diyagram şeklinde gösterilir. Graflar ayrık matematikte çalışmanın amaçlarından biridir.

Kenarlar yönlü veya yönsüz olabilir. Örneğin, düğümler bir partideki insanları temsil ediyorsa ve iki kişi arasında el sıkışırlarsa bir kenar varsa, o zaman bu grafik yönlendirilmez, çünkü herhangi bir A kişisi B kişisiyle ancak B ile A el sıkışırsa el sıkışabilir. Aksine, eğer bir A kişisinden bir B kişisine herhangi bir kenarı A hayranlığı B'ye karşılık gelirse, o zaman bu graf yönlendirilir, çünkü hayranlık zorunludur. İlk graf türüne yönsüz çizge, sonraki graf türüne yönlü çizge denir.

Çizgeler, graf teorisi tarafından incelenen temel konudur. "Graf" kelimesi ilk olarak bu anlamda 1878'de James Joseph Sylvester tarafından kullanılmıştır.[2][3]

Tanımlar

Çizge teorisindeki tanımlar değişkendir. Aşağıdakiler, grafları ve ilgili matematiksel yapıları tanımlamanın daha temel yollarından bazılarıdır.

Graf

Üç köşeli ve üç kenarlı bir graf.

Graf (Bazen ayırt etmeye yönelik sınıflandırırken, yönsüz graf ve yönlü graf veya basit graf, katlı graf olarak adlandırılırlar) [4][5] bir çift elemandan oluşur G = (V, E), V elemanına köşe denir ve E elemanı kenarlar (bazen bağlantılar veya çizgiler) olarak adlandırılan iki kümeden (iki ayrı öğeye sahip - iki kenar ve bağlayan çizgi- kümeler) oluşan bir dizidir. Her kenar iki ucunda düğüm olacak şekilde tanımlanır.

Bir kenarın {x, y}, düğümleri olan x ve y kenarların uç noktalarıdır. Kenar x ve y'yi ileşkilendirir ve x ve y'yi birbirine bağlar. Bir düğüm herhangi bir kenara ait olmayabilir.

Bir katlı graf, aynı köşe çiftine bitişik çoklu kenarlara izin veren bir genellemedir. Bazı metinlerde katlı graflara basitçe graflar da denir. [4][6]

Yönlü çizge

Üç köşeli ve dört yönlendirilmiş kenarlı yönlü bir graf (çift ok her yöndeki bir kenarı temsil eder).

Yönlü graf veya digraf, kenarların oryantasyonlu-yönlendirilmiş olduğu bir graftır.

Karışık graf

Ağırlıklı graf

On köşeli ve on iki kenarlı ağırlıklı bir grafik.

Graf çeşitleri

Yönlendirilmiş graf

Düzenli graf

Tam graf

Sonlu graf

Bağlı graf

İki parçalı graf

Yol graf

Düzlemsel graf

Çember graf

Ağaç

Çoklu ağaç

Gelişmiş sınıflar

Grafların özellikleri

Örnekler

Graf işlemleri

Genellemeler

Ayrıca bakınız

  • Kavramsal graf
  • Graf (soyut veri türü)
  • Graf veritabanı
  • Graf çizimi
  • Graf teorisi konularının listesi
  • Graf teorisi yayınlarının listesi
  • Ağ teorisi

Notlar

  1. ^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. s. 19. ISBN 978-0-486-67870-2. 5 Mayıs 2019 tarihinde kaynağından arşivlendi. Erişim tarihi: 8 Ağustos 2012. A graph is an object consisting of two sets called its vertex set and its edge set. 
  2. ^ Bakınız:
  3. ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. s. 35. ISBN 978-1-58488-090-5. 
  4. ^ a b Bender & Williamson 2010.
  5. ^ Bknz: Iyanaga and Kawada, 69 J, s. 234 veya Biggs, s. 4.
  6. ^ Graham et al., p. 5.

Kaynakça

Konuyla ilgili yayınlar

Dış bağlantılar

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Matematik</span> nicelik, yapı, uzay ve değişim gibi konularla ilgilenen bilim dalı

Matematik ; sayılar, felsefe, uzay ve fizik gibi konularla ilgilenir. Matematikçiler ve filozoflar arasında matematiğin kesin kapsamı ve tanımı konusunda görüş ayrılığı vardır.

<span class="mw-page-title-main">Çizge teorisi</span> nesneler arasındaki ikili ilişkileri modellemek için kullanılan matematiksel yapılar olan grafiklerin incelenmesi

Graf teorisi, çizge teorisi veya çizit teorisi, 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 oluşur.

<span class="mw-page-title-main">Sicim teorisi</span> makro ve mikro kosmosun teorilerini birleştirmeye çalışan teori. (her şeyin teorisi)

Sicim teorisi, parçacık fiziğinde, kuantum mekaniği ile Einstein'in genel görelilik kuramını birleştiren bir teori. "Sicim" adı, klasik yaklaşımda "sıfır boyutlu noktalar" şeklinde tarif edilen atomaltı parçacıkların, aslında "bir boyutlu ve ipliksi varlıklar" olabileceği varsayımına dayanır.

<span class="mw-page-title-main">Lineer cebir</span> Uzay matematiği

Doğrusal cebir ya da lineer cebir; matematiğin, vektörler (yöney), vektör uzayları, doğrusal dönüşümler, doğrusal denklem takımları ve matrisleri (dizey) inceleyen alanıdır. Vektör uzayları, modern matematiğin merkezinde yer alan bir konudur. Bundan dolayı doğrusal cebir hem soyut cebirde hem de fonksiyonel analizde sıkça kullanılır. Doğrusal cebir, analitik geometri ile de alakalı olup sosyal bilimlerde ve fen bilimlerinde yaygın bir uygulama alanına sahiptir.

Veri yapısı, bilgisayar ortamında verilerin etkin olarak saklanması ve işlenmesi için kullanılan yapı.

<span class="mw-page-title-main">Yarıçap</span> merkezinden çevresine bir daire veya küre içinde bölüm veya yüzeyi ile uzunluğu

Yarıçap, bir daire veya kürenin özeğinin (merkezinin) çemberine olan mesafesidir. Çapın yarısına eşittir.

<span class="mw-page-title-main">Kuantum alan teorisi</span> hareketli parçacık sistemlerinin kuantizasyonuyla ilgilenen parçacık mekaniğiyle benzer olarak, alanların hareketli sistemlerine parçacık mekaniğinin uygulamasıdır

Kuantum Alan Teorisi (METATEORİ); Klasik Birleşik Alan (KAT) Teorilerini, Özel Görekliliği (SRT), Kuantum mekaniği (KM) teorilerini tek bir teorik çerçeve altında toplayan bir üst teoridir.

Karar teorisi matematik ve istatistikte; değerlerin, belirsizlikler ve diğer konularla ilgili tespiti ile bir karar verme ve elde edilen optimum karar ile ilgilenir. Kararları birbirini etkileyen, çıkar çatışması içinde olan oyuncu etkileşimleri hasebiyle oyun kuramı ile yakından ilgilidir.

Hamilton Yolu, yönlü veya yönsüz bir grafta Hamilton yolu veya Hamilton devresinin olup olmadığının kararının verilmesinin problemidir.

<span class="mw-page-title-main">İki parçalı yarım</span>

Graf teorisinde, düğüm kümesi G = (U,V,E) olarak gösterilen iki parçalı graf'ın U veya V parçaları, "U'da bulunan her ui ve uj düğümü için, G üzerinden geçen ve 2(iki) uzunluğunda olan bir uiuj geçişi vardır" koşulunu sağlıyorsa, (konuşma diliyle G iki parçalı grafının yarısı anlamına gelecek şekilde) İki parça yarım (bipartite half) veya olarak adlandırılır.

<span class="mw-page-title-main">İki parçalı graf</span>

Graf teorisinde, düğümleri her kenar iki kümede de birer bitiş ucuna sahip olacak şekilde iki ayrı kümeye ayrılabilen graflara iki parçalı graf adı verilir.

<span class="mw-page-title-main">Bayes ağı</span>

Bir Bayes ağı, Bayes modeli ya da olasılıksal yönlü dönüşsüz çizge modeli bir olasılıksal çizge modelidir ve birbirleriyle koşulsal bağımlılıklara sahip bir rassal değişkenler kümesini yönlü dönüşsüz çizge(YDÇ) şeklinde ifade eder. Bayes ağları; gündelik hayatta meydana gelen bir olayı anlatmak ve o olayın gerçekleşmesine sebebiyet verebileceği bilinen birkaç olası nedenden herhangi birinin katkıda bulunan faktör olma olasılığını tahmin etmek için kullanılan ideal bir modelleme türüdür. Örneğin, bir Bayes ağı kullanılarak hastalıklar ve semptomları arasındaki olasılıksal koşul ilişkileri modellenebilir. Bu model kullanılarak, bir kişide görülen semptomlar verildiğinde bu kişinin bazı hastalıklara sahip olma olasılıkları hesaplanabilir. Buna benzer olarak neden-sonuç ilişkisi olan birçok olayın olasılığı bu modelleme ile görselleştirilebilir.

<span class="mw-page-title-main">Düğüm (matematik)</span> grafik teorisinde, bir grafikteki diğer birimlerle, kenarlarla bağlantılı birim

Düğüm matematikte ve özellikle çizge teorisinde, bir çizgeyi oluşturan temel elemandır. Bir çizge temel olarak düğüm ve kenarlardan oluşur. Çizge görselleştirilirken genellikle düğümler çember, kenarlar da çizgi veya ok şeklinde gösterilir.

<span class="mw-page-title-main">Temsil teorisi</span>

Temsil teorisi soyut cebirdeki cebirsel yapıları, daha somut olan matematiksel nesnelerin dönüşümleri olarak tasvir etmeye çalışan bir matematik dalıdır. Örneğin soyut bir grubunu bir vektör uzayı 'nin eşyapı dönüşüm grubunun() içinde görmeye çalışır. Böyle temsillere doğrusal temsil denir, çünkü bu temsil aslında grubundan genel lineer grup 'ye bir morfizma yazmak demektir. Böyle bir temsil bulmaktaki amaç, grubunu çalışmak için lineer cebir kullanmaktır. Soyut gruplardaki çarpma işlemi, özellikle bir bilgisayar için matris çarpmasından daha zordur. Soyut bir grubun doğrusal temsillerini kullanarak, gruptaki kimi hesaplamaları bilgisayara yaptırmak daha kolay olur.

<span class="mw-page-title-main">Derin öncelikli arama</span>

Bilgisayar biliminde, derin öncelikli arama, ağaç ya da çizge veri yapılarında arama yapmak için kullanılan bir algoritmadır. Algoritma aramaya başladığı düğümden ulaşabileceği en derin düğüme kadar gider, gidecek daha derin bir düğüm kalmadığında geri sarar ve derin düğümlere öncelik vererek gezmeye devam eder.

<span class="mw-page-title-main">Yönlü çizge</span> yönlendirilmiş kenarlara sahip grafik

Çizge teorisinde, yönlü çizge düğümler ve hepsi birer yöne sahip kenarlardan oluşan çizgedir.

<span class="mw-page-title-main">Elektron iyonizasyonu</span>

Elektron iyonizasyonu, enerjik elektronların iyonlar üretmek için katı veya gaz fazı atomları veya molekülleri ile etkileşime girdiği bir iyonizasyon yöntemidir. EI, kütle spektrometrisi için geliştirilen ilk iyonizasyon tekniklerinden biriydi. Ancak bu yöntem hala popüler bir iyonizasyon tekniğidir. Bu teknik, iyonları üretmek için yüksek enerjili elektronlar kullandığı için sert bir iyonizasyon yöntemi olarak kabul edilir. Bu, bilinmeyen bileşiklerin yapı tespiti için yardımcı olabilecek kapsamlı parçalanmaya yol açar. EI, moleküler ağırlığı 600'ün altında olan organik bileşikler için en yararlı olanıdır. Aynı zamanda, katı, sıvı ve gaz halindeki birkaç başka termal olarak kararlı ve uçucu bileşik, çeşitli ayırma yöntemleriyle birleştirildiğinde bu tekniğin kullanılmasıyla tespit edilebilir.

<span class="mw-page-title-main">Batlamyus eşitsizliği</span>

Öklid geometrisinde, Batlamyus eşitsizliği, düzlemde veya daha yüksek boyutlu bir uzayda dört nokta tarafından oluşturulan altı uzunluğu ilişkilendirir. Herhangi bir A, B, C ve D noktası için aşağıdaki eşitsizliğin geçerli olduğunu belirtir:

.

Bilgisayar biliminde, Floyd-Warshall algoritması kenar ağırlıkları artı ya da eksi değere sahip çizgelerde en kısa yolları bulma algoritmasıdır. Algoritma uygulandığında her düğüm çifti için en kısa yol uzunluklarını bulur. Özgün algoritma yol detaylarını döndürmese de, küçük değişikliklerle yolların oluşturulması da mümkündür. Çizge kuramında ve diğer matematik uygulamalarında kullanılır.

Norman Linstead Biggs, ayrık matematik ve özellikle cebirsel kombinatorik üzerine odaklanan önde gelen bir İngiliz matematikçidir.