كليدواژه زبان طبيعي :
گراف ها(رياضيات ) , گراف هاي مجاور , الگوريتم ها , برنامه هاي كامپيوتري , گراف هاي مسطح , گراف همسايه نسبي , گراف گالريل , گراف دلوني , رنگ آميزي (گراف ها) , بخش رياضي كاربردي , رنگ كردن (رياضيات )
چكيده :
در اين مقاله گرافهاي خاصي را كه در حل مسايل متعددي از زمينه ها از قبيل ، رياضيات ، مهندسي ، فيزيك ، علوم كامپيوتر، طرح زمان بندي شده ، هوش مصنوعي و ... مفيد هستند، مورد بررسي قرار خواهيم داد. گرافهايي كه در نظر مي گيريم اقليدسي هستند يعني در فضاي R ، با فاصله اي كه روي متر اقليدسي بنا شده است . همچنين فرض مي كنيم كه مجموعه ريوس ، كه يالها از آنها مي گذرند، ناتباهيده باشند يعني هيچ چهار راس هم دايره نباشند، زيرا مجموعه نقاط تباهيده ممكن است نامسطح باشند. سه خانواده از گراف هاي مجاور مسطح را تشريح خواهيم كرد. اين گرافها عبارتند از: 1- گراف همسايه نسبي 2- گراف گابريل 3- گراف دلوني همچنين علاوه بر خاصيت هاي گراف هاي ذكر شده مسيله رنگ آميزي نيز مطرح مي شود. هدف اين است كه نشان دهيم چگونه وقتي به بعضي از گراف هاي مجاور محدود شويم مسايل رنگ آميزي آنها اغلب در مقايسه با گراف هاي دلخواه يا حتي گراف هاي مسطح كلي ، آسانتر خواهد شد. دو دليل اصلي براي اين موضوع اين است كه اولا" گرافهاي مجاور با توجه به زير گراف هاي مجاور بطور ميانگين تنك تر از گراف هاي مسطح كلي مي باشند. همانطور كه خواهيم ديد اين دو خاصيت به ما اجازه مي دهد كه الگوريتم هايي با زمان پيچيدگي كمتر براي آنها طرح شود.
