گراف روابط آشنایی

از مدل‌های گراف می‌توانیم برای نمایش روابط متعدد بین افراد استفاده کنیم.

برای مثال، می‌توانیم از یک گراف ساده برای نمایش این که آیا دو نفر همدیگر را می شناسند، یعنی آیا آشنا هستند، استفاده کنیم.

در یک گروه خاص از افراد، هر فرد لت یک رأس نمایش داده می‌شوند. هیچ یال چند گانه و معمولاً هیچ حلقه ای بکار نمی‌رود. (اگر بخواهیم مفهوم خودشناسی را نیز در نظر بگیریم، حلقه خواهیم داشت)

در شکل روبرو یک گراف روابط آشنایی ساده نشان داده شده است.

گراف روابط آشنایی تمام انسان‌ها در جهان بیش از شش میلیارد رأس و احتمالاً بیش از یک تریلیون یال دارد.

مسیرها در گراف‌های روابط آشنایی

در یک گراف روابط آشنایی، مسیر بین دو فرد وجود دارد، اگر یک زنجیره از مردم متصل کننده این افراد، وجود داشته باشد که دو فرد در زنجیره مجاورند، اگر یکدیگر را بشناسند.

بسیاری از دانشمندان اجتماعی حدس زده‌اند که تقریباً هر زوج از افراد جهان توسط یک زنجیره کوچک از افراد شاید شامل تمام افراد جهان توسط مسیر با طول نابیشتر از چهار به هم وصل هستند.

فیلم شش درجه جدایی با بازی جان گار مبتنی برا این مفهوم است.

Kenneth H, Rosen (1998). "Number Theory and Cryptography". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007.