پاورپوینت نظریه گراف و کاربرد آن

در دنیای اطراف ما، وضعیف های فراوانی وجود دارند كه می توان توسط نموداری متشكل از یك مجموعه نقاط ، به علاوه خطوطی كه برخی از این نقاط را به یكدیگر متصل می كنند، به توصیف آنها پرداخت، به عنوان مثال ، برای نشان دادن رابطه دوستی بین یك دسته از انسان ها می نوانیم هر شخص را با یك نقطه مشخص كنیم . نقاط متناظر با هر دو دوست را با یك خط به یكدیگر وصل نماییم، یا در جای دیگر ممكن است برای نشان دادن یك شبكه ارتباطی، از نموداری استفاده كنیم كه در آن ، نقاط نمایانگر مراكز ارتباطی و خطوط، نشان دهنده پیوندهای ارتباطی بین مراكز باشند. توجه داشته باشید كه در این گونه نمودارها، آن چه بیشتر مورد توجه است این است كه آیا دو نقطه داده شده ، به وسیله یك خط به یكدیگر متصل هستند یا نه و طریقه اتصال آنها اهمیتی ندارد. تجربه ریاضی این وضعیت ها به مفهوم گراف منتهی می شود.

نمودار یك گراف ، فقط رابطه وقوعی را كه بین راس ها و یال ها برقرار است، نشان می دهد، با این حال در غالب اوقات ، نموداری از یك گراف را رسم كرده ، به جای خود گراف ، به نمودار آن اشاره می كنیم. به همین منوال نقطه های آن را «راس» و خطوط آن را «یال» می نامیم.

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

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