دنباله گرافی

دنباله گرافی

دنباله‌ای مرتب از اعداد (صعودی یا نزولی) مانند $d_{1},d_{2},...,d_{p}$ را دنباله گرافی می‌نامند هرگاه بتوان گرافی ساده با $p$ راس رسم کرد که درجه راس‌های آن همین اعداد باشد.

تشخیص دنباله گرافی

۱. در هر گراف ساده از مرتبه $p$درجه هر راس حداکثر $p-1$ است. مثلاً دنباله $1,2,3,4$ مربوط به گراف ساده نیست چون ۴ راس داریم و نمی‌توانیم راس درجه ۴ داشته باشیم.

۲. تعداد راس‌های فرد هر گراف عددی زوج است چون اگر تعداد راس‌های فرد، عددی فرد باشد. جمع درجه‌ها برابر عدد زوج $2p$ نمی‌شود. مثلاً دنباله ی $1,2,2,3,4,5$ مربوط به گراف ساده نیست چون سه راس فرد در گراف وجود دارد.

نتیجه: تعداد راس‌های زوج هر گراف، از نظر زوج و فرد بودن هم جنس مرتبه گراف است یعنی اگر $p$ زوج باشد تعداد راس‌های زوج هم عددی زوج است و اگر $p$ فرد باشد تعداد راس‌های زوج هم عددی فرد است.

۳. اگر گراف دارای $k$رأس فول باشد، آنگاه باید $\delta \geq k$ باشد، مثلاً دنبالهٔ $1,1,3,3,5,5$ مربوط به گراف ساده نیست چون دو راس فول داریم باید $\delta \geq 2$ باشد که اینطور نیست و $\delta =1$ است.

۴. حداقل دو راس گراف، دارای یک درجه‌اند، یعنی دنباله گرافی باید حداقل دو جملهٔ مساوی داشته باشیم، مثلاً دنباله $3,2,1,0$ مربوط به گراف ساده نیست چون حداقل دو جمله مساوی ندارد.

۵. در تشخیص گرافی بودن یک دنباله، می‌توانیم از راس‌های درجهٔ صفر نظر کنیم یعنی می‌توانیم جمله‌های صفر را از دنباله پاک کنیم. مثلاً به جای بررسی دنباله $3,3,2,2,0,0,0$ می‌توانیم دنباله$3,3,2,2$ را بررسی کنیم.

الگوریتم هاول – حکیمی

دنباله‌هایی وجود دارند که همه نکات فوق در آن‌ها برقرار است، اما دنباله، مربوط به یک گراف ساده نیست. به عنوان مثال دنبالهٔ $5,5,4,4,2,2$ در اینگونه موارد می‌توان به کمک الگوریتم، دنبالهٔ درجات را سبک می‌کنیم که در نتیجه تشخیص گرافی بودن دنبالهٔ حاصل از دنباله اولیه ساده‌تر است. اما روش کار به صورت زیر است:

گام ا: دنباله را به صورت نزولی مرتب می‌کنیم.

گام ۲: بزرگترین عدد دنباله یعنی $A$ را حذف کرده و از $A$راس بعدی یک واحد کم می‌کنیم (مشتق اولیه دنباله)

گام ۳: می‌توان گام‌های فوق را تا جایی که تشخیص دنبالهٔ حاصل میسر شود ادامه داد (مشتق nام)

توجه: اگر دنباله‌ای مربوط به گراف ساده باشد پس از به کار بردن الگوریتم هاول – حکیمی تا مرحله آخر، به دنباله‌ای می‌رسیم که تمام جملاتش صفر است.

منابع

Kenneth H, Rosen (1998). "Graphs". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007. {{cite book}}: Check date values in: |بازبینی= (help)

• https://en.wikipedia.org/wiki/Sequence_graph.

• https://en.wikipedia.org/wiki/Havel–Hakimi_algorithm.