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

بررسی و تحلیل نظریه گراف
بررسی و تحلیل نظریه گراف
90,000 ریال 
تخفیف 15 تا 30 درصدی برای همکاران، کافی نت ها و مشتریان ویژه _____________________________  
وضعيت موجودي: موجود است
تعداد:  
افزودن به ليست مقايسه | افزودن به محصولات مورد علاقه

تعداد صفحات: 70 صفحه _ فرمت WORD _ دانلود مطالب بلافاصله پس از پرداخت آنلاین

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


گرافها
پیشگفتار:
سازمانی را در نظر بگیرید که برای انجام کارهای خود ٦ کامپیوتر دریافت کرد است. در تلاش برای بالا بردن خدماتی که کامپیوتر می تواند عرضه کند، این سازمان تصمیم دارد کامپیوترها را به گونه ای به هم متصل کند، تا تشکیل یک سیستم یکپارچه را بدهد. با این حال، در این سیستم لازم نیست هر کامپیوتر به همۀ کامپیوترهای دیگر متصل باشد. در حقیقت آشکار است که اتصال زیر، بهترین اتصال بین این کامپیوترها است:
کامپیوتر 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 و به ازای هر،  
١-یک یال از هر رأس   به هر رأس   موجود باشد؛
٢-یک یال از هر رأس   به هر رأس دیگر   موجود نباشد؛
٣-یک یال از هر رأس   به هر رأس دیگر   موجود نباشد.

نظري براي اين محصول ثبت نشده است.


نوشتن نظر خودتان

براي نوشتن نظر وارد شويد.

محصولات
نظر سنجي
نظرتون در مورد ویکی پروژه چیه؟
  •   مراحل ثبت نام خیلی زیاده!
  •   مطلب درخواستیم رو نداشت!
  •   ایمیل نداشتم که ثبت نام کنم!
  •   مطلبی که میخواستم گرون بود!
نظرنتيجه