نظریه گراف - چند گراف پر کاربرد

[bahar_m]

نظریه گراف - چند گراف پر کاربرد :

مقدمه :

فرض کنید V یک مجموعه ناتهی و E زیرمجموعه‌ای از باشد در این صورت زوج را یک گراف می نامند.V را مجموعه راس ها و E را مجموعه یال ها می گویند. اگر ترتیب قرار گرفتن راس ها در مجموعه E مهم باشد،گراف را گراف جهت دار می گویند و یال از راس به سمت راس را به صورت نشان می‌دهند.در غیر این صورت گراف را بدون جهت می‌نامند و یال بین راس های و با نماد نشان می‌دهند.

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


گراف کامل :
یک گراف کامل ،گرافی است که هر بین هر دو راس آن دقیقا یک یال وجود داشته باشد.
نکته : اگر گراف شما یک چند ضلعی باشد بطوریکه راسهای گراف شما زاسهای زوایای این چند ضلعی باشند، تمام قطر های چند ضلعی و اضلاع آن تشکیل یک گراف کامل میدهند ؛ پس :
- یک گراف کامل از مرتبه n،دارای n راس و یال است و آن را با نشان می‌دهند.
2-یک گراف کامل یک گراف منتظم از درجه n-1 است.


گراف دو بخشی :

گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونه ای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف می نامند.

گراف دو بخشی کامل : ک گراف دو بخشی است که مجموع رئوس آن به دو مجموعه X و Y چنان افراز شده است و هر راس در ان به هر راس وصل شده است. گراف دو بخشی کامل را با نماد نشان می دهند که در آن m تعداد عناصر مجموعه X و n تعداد عناصر مجموعه Y است.


گراف چرخ :

هر گراف که دارای راس باشد که و یکی از رئوس از درجه ی و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامیم ؛ مانند :


گراف بازه ای :
فرض می کنیم مجموعه ای از بازه های باز داریم. اگر این بازه ها را به عنوان رئوس و اتصال دو راس را، به شرط ناتهی بودن اشتراک بازه های متناظر، یال ها در نظر بگیریم، گرافی می توان رسم کرد که به آن گراف بازی ها میگوییم. به عبارت دریگر گراف بازه ای متناظر با بازی های باز گرافی است که رئوس آن بازه های باز بوده و در صورتی دو راس مجاورند(میانشان یال وجود دارد) که بازه های متناظر آن دو راس اشتراک ناتهی داشته باشند.

یک مثال :