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

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

گراف G یک سه تایی مرتب