Sözlük

Soldaki anahtar kelimelerden birini seçin…

Grafikler ve AğlarEl Sıkışma ve Flört

Okuma zamanı: ~15 min
Bu sayfa otomatik olarak çevrilmiştir ve hatalar içerebilir. Çevirileri incelememize yardımcı olmak istiyorsanız lütfen iletişime geçin!

Arkadaşlarınızla birlikte harika bir doğum günü partisine davet edildiniz. Kendiniz ve ev sahibi dahil olmak üzere ${hnd} insanlar mevcut.

Akşamları, konuklar ayrılmaya hazırlanırken, herkes diğer herkesle el sıkışır. Toplamda kaç el sıkışma var?

El sıkışmalarını bir grafik kullanarak temsil edebiliriz: her insan ve her el sıkışma .

Şimdi grafikteki kenar sayısını saymak kolaydır. Orada buluyoruz ${hnd} insanlar var ${hnd*(hnd-1)/2} tokalaşma.

Büyük grafiklerde tüm kenarları saymak yerine, herhangi bir sayıda konuk için sonucu bize bildiren basit bir formül bulmaya çalışabiliriz.

Her biri ${n} partide insanlar ile el sallar ${n-1} diğerleri. Bu yapar ${n} x ${n-1} = ${n×(n-1)} toplam el sıkışma. N kişi için, el sıkışma sayısı .

Ne yazık ki bu cevap pek doğru değil. Nasıl olduğunu fark et üst satırdaki ilk iki giriş aslında aynı, sadece çevrilmiş.

Aslında, her el sıkışmasını saydık , ilgili iki kişinin her biri için bir kez. Bu, doğru el sıkışma sayısının ${n} misafir ${n}×${n-1}2=${n*(n-1)/2} .

El sıkışma grafikleri özeldir çünkü her tepe noktası diğer tepe noktalarına bağlıdır. Bu özelliğe sahip grafiklere tam grafik denir. 4 köşeli tüm grafik genellikle şu şekilde kısaltılır: K4 , 5 köşeli tüm grafik olarak bilinir K5 , ve bunun gibi.

Az önce n köşe, Kn , vardır n×n12 kenarları.

Farklı bir günde, için bir hızlı tanışma etkinliğine davet edildiniz ${m} erkekler ve ${f} kızlar. Birçok küçük masa var ve her oğlan her bir kız ile 5 dakika geçiriyor. Toplamda kaç tane “tarih” var?

Bu durumda, karşılık gelen grafik iki ayrı köşe kümesinden oluşur. Her köşe tüm köşelere bağlanır seti, ama köşe noktaları yok küme. Bu düzene sahip grafiklere iki taraflı grafikler denir.

X ve y boyutlarında iki takım içeren iki taraflı grafik genellikle şu şekilde yazılır: Kx,y . Vardır kenarları, yani yukarıdaki örnekte ${m} x ${f} = ${m×f} tarih.

Archie