فایل کامل و عالی بررسی و تحلیل نظریه گراف

فصل اول : گراف ها   
پیشگفتار    
تعریف گراف   
گراف های خاص   
تعریف و نمادگذاری   
مفهوم درجه یک راس   
گزاره    
فصل دوم : مسیرها و دور ها   
همبندی   
دورهای اویلری    
عکس نقض قضیه   
دورهای همیلتونی    
فصل سوم : گراف ها و ماتریس ها   
نمایش ماتریسی گراف ها   
ماتریس ها   
ماتریس و گرافهای جهت دار   
ماتریس ها و گراف های بدون جهت    
ضرب ماتریس ها   
شمارش گردش هایی به طول N   
فصل چهارم : یکریختی گراف ها   
فصل پنجم : درخت ها   
مقدمه   
مشخصه درخت ها   
بخش دوم – درخت های ریشه دار    
درخت های دودویی   
فصل ۶ : درخت های فراگیر   
مقدمه    
گزاره    
درخت فراگیر حداقل   
الگوریتم کراسکل   
الگوریتم پریم

گرافها
پیشگفتار:
سازمانی را در نظر بگیرید که برای انجام کارهای خود ۶ کامپیوتر دریافت کرد است. در تلاش برای بالا بردن خدماتی که کامپیوتر می تواند عرضه کند، این سازمان تصمیم دارد کامپیوترها را به گونه ای به هم متصل کند، تا تشکیل یک سیستم یکپارچه را بدهد. با این حال، در این سیستم لازم نیست هر کامپیوتر به هم? کامپیوترهای دیگر متصل باشد. در حقیقت آشکار است که اتصال زیر، بهترین اتصال بین این کامپیوترها است:
کامپیوتر A را به کامپیوترهای B و C و D و E متصل کنید؛
کامپیوتر B را به کامپیوترهای A و C متصل کنید؛
کامپیوتر C را به کامپیوترهای A، B، D و E متصل کنید؛
کامپیوتر D را به کامپیوترهای A و C متصل کنید؛
کامپیوتر E را به کامپیوترهای A، C و F متصل کنید؛
کامپیوتر F را به کامپیوتر E متصل کنید؛
به راحتی می توان این اطلاعات را با نمودار شکل زیر نمایش داد:
 
( شکل ۱.

برای مشاهده محصول مشابه پیشنهاد می‌کنیم فایل کامل و عالی مقاله نظریه تولمن را ببینید.

۱ )
نموداری مانند نمودار بالا را، یک گراف می نامند. در این نمودار، نقطه ها را رأس های گراف و پاره خطهایی که رأسها را به هم متصل می کند، یالهای گراف می نامند. همان گونه که از شکل پیدا است؛ امکان دارد دو یال یکدیگر را در یک نقطه قطع کنند که رأس گراف نباشد. هم چنین توجه دارید که نوع چنین نموداری با آن چه که به وسیله « نمودار یک معادله » یا « نمودار یک تابع » رسم می شود، کاملاً متفاوت است. به طور کلی یک گراف از یک مجموعه از رأسها و یک مجموعه از یالها تشکیل می شود، که یالهای آن، رأس های مجزا را به هم متصل می کند. یال می تواند به صورت خط راست یا منحنی باشد، که از یک رأس به رأس دیگر از یک رأس به خود آن رأس وصل می شود. شکل زیر را ببنید.
 
( شکل ۲.۱ )
در شکل بالا، رأسها را با v و یالها را با e برچسب گذاری کرده ایم.
هر گاه یک یال، رأسی را به خود آن رأس متصل کند ( مانند یال   در شکل بالا )به آن حلقه می گویند و هر گاه دو یال، از اتصال دو رأس یکسان به وجود آید ( مانند یال های   و   )، به آنها، یالهای موازی می گویند. البته امکان دارد، که یک رأس با هیچ یالی به رأس دیگر متصل نباشد ( مانند رأس   )، در این صورت به آن، رأس منفرد می گویند.

تعریف گراف چنین است:
تعریف:
گراف G از دو مجموع? متناهی تشکیل شده است: ( G )V ( مجموع? رأسها ) و ( G )E ( مجموع? یالها )، که در آن هر یال با مجموعه ای شامل یک یا دو رأس، به نام « نقاط پایانی » یا « نقاط دوسر » متناظر است. تناظر یالها به نقاط پایانی، تابع یال- نقطه پایانی نامیده می شود و یالی که فقط یک نقط? پایانی داشته باشد، حلقه نام دارد. دو یال مجزا، با مجموع? یکسان از نقاط پایانی، یالهای موازی نامیده می شود. هر یال به نقاط پایانی خود متصل است. دو رأسی را که به وسیل? یک یال به هم متصل شده باشد، دو رأس مجاور می گویند و رأسی که نقطه پایانی یک حلقه باشد، مجاور به خود نامیده می شود. یک یال به هر یک از دو نقط? پایانی خود محدود است و دو یالی را که محدود به یم نقط? پایانی است، دو یال مجاور می گویند. به رأسی که شامل هیچ یالی نیست، رأس منفرد می گویند. گرافی که هیچ رأسی نداشته باشد، گراف تهی و گرافی که حداقل یک رأس داشته باشد، گراف غیر تهی نام دارد.

گرافها دارای نمایش تصویری هستند که در آن رأسها را با نقطه و یالها را با پاره خط نمایش می دهند. هر نمایش مفروض، به طور منحصر بفردی یک گراف را نشان می دهد.
تعریف:
یک گراف جهت دار  G از دو مجموع? متناهی تشکیل شده است: مجموع? رأسها ( G )V و مجموع? یالها ( G )E که در آن هر یال متناظر با یک زوج مرتب از رأسها موسوم به نقاط پایانی یا نقاط دو سر آن است، اگر یال e متناظر با زوج ( v , w ) از رأسها باشد، e را یال ( جهت دار ) از v به w گویند.

گرافهای خاص:
یک دست? قابل توجه و مهم از گرافها، شامل گرافهایی است که دارای حلقه یا یالهای موازی نیستند. به چنین گرافهایی، گرافهای ساده می گویند. در یک گراف ساده هیچ دو یالی دارای مجموعه نقاط پایانی یکسان و مشترک نیستند، از این رو، در گراف ساده یک یال با مشخص شدن دو نقط? پایانی معین می شود.

تعریف و نمادگذاری:
یک گراف ساده، گرافی است که هیچ حلقه یا یال موازی نداشته باشد.
در یک گراف ساده یک یال با نقاط پایانی v و w، با   نمایش داده می شود.

تعریف:
یک گراف کامل با n رأس، با   نمایش داده می شود، یک گراف ساده با n رأس   است که مجموعه یالهای آن به گونه ای است که هر زوج رأس متمایز آن دقیقاً شامل یک یال است.
تعریف:
یک گراف کامل دو بخشی با ( m , n ) رأس که با   نمایش داده می شود، یک گراف ساده با رأسهای   و   است که در خاصیت های زیر صدق کند: به ازای هر، m و …   و i و به ازای هر،  
۱-یک یال از هر رأس   به هر رأس   موجود باشد؛
۲-یک یال از هر رأس   به هر رأس دیگر   موجود نباشد؛
۳-یک یال از هر رأس   به هر رأس دیگر   موجود نباشد.