گراف‌های تماس تلفنی

می توان از گراف‌ها برای مدل کردن تماس‌های تلنفی برقرار شده در یک شبکه مانند شکبه تلفن راه دور استفاده کرد. به‌طور خاص، می‌توان از یک گراف چندگانه جهت دار برای مدل کردن تماس‌های تلفنی استفاده کرد که در ان هر شماره تلفن، با یک راس[1]و هر تماس تلفنی با یک یال[2] جهت دار نمایش داده می‌شود. یالی که یک تماس تلفنی ر انشان می‌دهد از راس مربوط به شماره تلفن تماس گیرده شروع شده و به راس مربوط به شماره تلفن مقصد ختم می‌شود. ازانجایی که جهت تماس برقرار شده حائز اهمیت است نیاز بخ یال‌های جهت داریم، چون می‌خواهیم تمامی تماس‌های گرفته شده از یک شماره تلفن خاص به شماره دوم را نمایش دهیم، نیاز به یال‌های جهت دار چندگانه داریم

مثال برای گراف تلفنی

برای گراف تلفنی دو مثال می‌توان زد که در ان یکی یال‌ها جهت دار و دیگری بی جهت است

جهت دار

در شکل زیر یک گراف تلفنی ساده نشان داده شده‌است که نمایش دهنده ۷ شماره تلفن است، در این کراف برای مقال مشاهده می‌شود که سه تلفنی از ۱۲۳۴-۵۵۵-۷۳۲ به ۹۸۷۶-۵۵۵-۷۳۲ و دو تماس تلفنی در جهت عکس برقرار شده‌است؛ ولی هیج تماسی از ۴۴۴۴-۵۵۵-۷۳۲ به هیج یک از ۶ شماره دیگر به جز ۰۰۱۱-۵۵۵-۷۳۲ برقرار نشده‌است،

بی جهت

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

اجزاء همبند گراف‌های تماس تلفنی

دو راس xوy در یک جزء از گراف تماس تلفنی قرار دارنذ اگر دنباله‌ای از تماس‌های تلفنی شروع شوند از x وختم شونده به y وجود داشته باشد. وقتی کراف تماس تلفنی برای تماس‌های تلفنی برقرار شده در طول یک روز خاص در شبمه AT&T تحلیل شد، این گراف شامل ۵۳٬۷۶۷٬۰۸۷ راس بیش از ۱۷۰ میلیون یال بیش از ۳٫۷ میلیون جزء همبند بود. بسیار از این اجزاء کوچک بودند، تقریباا سه چهارم آنها، شامل دو راس نمایش دهنده زوج شماره تلفن‌هایی بودند که فقط با همدیگر تماس گرفته بودند این گراف شامل یک چز<همبند بزرگ با ۴۴٬۹۸۹٬۲۹۷ راس، شامل بیش از ۸۰ کل رئوس است. علاوه برا این هر اس در این جزء به هر راس دیگر توسط یک زنجیره که بیشتر از ۲۰ تماس ندارد، متصل است

جستارهای وابسته

منابع
  1. یک راس را در گراف با V نشان می‌دهند و به ان نّد یا سریال هم می گوییند
  2. هر یال را در گراف با E نمایش می‌دهند که اتصال بین دور راس را مشخص می‌کند

Kenneth H, Rosen (1998). "Graph". Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. Check date values in: |بازبینی= (help)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.