Lüğət

Soldakı açar sözlərdən birini seçin ...

Qrafiklər və ŞəbəkələrƏl görüşmələri və Tanışlıq

Oxumaq vaxtı: ~15 min
Bu səhifə avtomatik tərcümə edildi və səhvlər ola bilər. Zəhmət olmasa tərcümələri nəzərdən keçirməyə kömək etmək istəyirsinizsə əlaqə qurun!

Dostlarınızla birlikdə gözəl bir doğum gününə dəvət aldınız. Özünüz və ev sahibi daxil olmaqla, var ${hnd} insanlar təqdim edir.

Axşam qonaqlar ayrılmağa hazırlaşdıqca hər kəs başqaları ilə əl sıxır. Cəmi neçə əl toplantısı var?

Bir qrafı istifadə edərək əl sıxışmalarını təmsil edə bilərik: hər bir şəxs və hər .

İndi qrafikdəki kənarların sayını saymaq asandır. Orada tapırıq ${hnd} insanlar var ${hnd*(hnd-1)/2} əl sıxma.

Bütün kənarları böyük qrafiklərdə saymaqdansa, istənilən sayda qonaq üçün nəticəni izah edən sadə bir düstur tapmağa da cəhd edə bilərik.

Hər biri ${n} Yığıncaqdakı insanlar əl sıxır ${n-1} digərləri. Bu edir ${n} × ${n-1} = ${n×(n-1)} ümumilikdə əl sıxma. N insanlar üçün əl sıxma sayı olardı .

Təəssüf ki, bu cavab düzgün deyil. Diqqət yetirin üst sıra ilk iki giriş əslində eynidır, sadəcə ətrafa yuvarlanıblar.

Əslində hər əl sıxmağı saydıq , cəlb olunan iki nəfərin hər biri üçün bir dəfə. Bu, düzgün əl yığmağın sayı deməkdir ${n} qonaqlar ${n}×${n-1}2=${n*(n-1)/2} .

Əl vermə qrafikləri xüsusi bir yerdədir, çünki hər vertex hər bir digər ucuna bağlıdır. Bu xassəyə malik qrafiklər tam qrafiklər adlanır. 4 ucu olan tam qrafik tez-tez olduğu kimi qısaldılır K4 , 5 ucu olan tam qrafik kimi tanınır K5 , və sair.

Biz yalnız ilə tam bir qrafik göstərdik n ucları, Kn , var n×n12 kənarları.

Fərqli bir gündə sizi sürətli bir tanışlıq tədbirinə dəvət edirsiniz ${m} oğlanlar və ${f} qızlar. Çox kiçik masalar var və hər oğlan qızların hər biri ilə 5 dəqiqə vaxt keçirir. Cəmi neçə fərdi "tarix" var?

Bu vəziyyətdə, müvafiq qrafik iki ayrı uc dəstindən ibarətdir. Hər bir vertex bütün uclarına bağlıdır dəsti, lakin heç birinin dəsti. Bu nizama sahib olan qrafiklərə iki tərəfli qrafiklər deyilir.

İki ölçüsü xy olan iki tərəfli qrafik tez-tez olduğu kimi yazılır Kx,y . Var kənarları, bu da yuxarıdakı misalda var deməkdir ${m} × ${f} = ${m×f} tarixləri.