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

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

گراف G یك سه تایی مرتب است كه تشكیل شده از یك مجموعه ناتهیV(G) از راس ها، یك مجموعه E(G) – مجزای از V(G) – از یال ها و یك تابع وقوع كه به هر یال G ، یك زوج نا مرتب از راس های G را – كه الزاماً متمایز نیستند – نسبت می دهد. اگر e یك یال وu ودو راس باشند به طوری كه ، در این صورت گفته می شود كه e، راس هایu و را به یكدیگر وصل كرده است و راس های u و  ، دو سر یال e نامیده می شوند.

دلیل نامگذاری گراف ها بدین نام، این است كه می توان آنها را به صورت گرافیكی نمایش داد و همین نمایش گرافیكی است كه ما را در درك بسیاری از خواص گراف ها یاری می كند. در این گونه نمایش داده می شود.

آشنایی با گراف

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

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

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

یك گراف ساده است، اگر هیچ طوقه ای نداشته باشد و بین هر دو راس آن ، بیش از یك یال نباشد . نمادهای  را به ترتیب برای نشان دادن تعداد راس ها و تعداد یال های گراف G به كار می بریم.