||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!درجه راسها
اگر{TEX()} {v\in V(G)} {TEX} باشد درجه راس {TEX()} {v} {TEX} را به طور ساده تعداد یالهایی تعریف می کنیم که{TEX()} {v} {TEX} بر آنها واقع است.
---
!!تبصره
در گراف های چندگانه طوقه را دوبار در درجه راس مربوط به حساب می آوریم.
•{TEX()} {\delta (G)} {TEX}.کوچکترین درجه در گراف{TEX()} {G} {TEX} را {TEX()} {\delta (G)} {TEX} تعریف می کنیم ( بخوانید دلتای کوچک {TEX()} {G} {TEX})
•{TEX()} {\Delta (G)} {TEX}. بزرگترین درجه در گراف{TEX()} {G} {TEX} را {TEX()} {\Delta (G)} {TEX}تعریف می کنیم ( بخوانید دلتای بزرگ{TEX()} {G} {TEX} ‌)
درجه راس {TEX()} {v} {TEX} را با {TEX()} {deg(v)} {TEX}یا{TEX()} {d(v)} {TEX} نمایش می دهیم.
---
!قضیه
در هر گراف {TEX()} {G} {TEX} با مجموعه رئوس{TEX()} {(v)} {TEX} که {TEX()} {G} {TEX} ساده باشد داریم:
@@{TEX()} {\forall v\in V : \ 0 \le d(v) < |V|} {TEX}@@
__اثبات__
به آسانی ثابت می شود، زیرا حداقل درجه هر راس می تواند صفر باشد یعنی به هیچ راس دیگری متصل نباشد و حداکثر درجه هر راس هم می تواند{TEX()} {|V|-1} {TEX} باشد یعنی به همه متصل باشد ( دقت کنید گراف ساده بوده پس بین هر دو راس حداکثر یک یال وجود خواهد داشت )
لذا به آسانی دیده می شود:
@@{TEX()} {0\le \delta (G) \le d(v) \le \Delta (G) \le |V|-1} {TEX}@@
---
!تمرین
گرافی مثال بزنید که به ازای هر{TEX()} {v\in V} {TEX} داشته باشیم: {TEX()} {\delta (G)=d(v)=\Delta (G)} {TEX}
به راحتی :
#@
@#16:
::{picture=img/daneshnameh_up/8/8b/mco0050a.jpg} ::
@@{TEX()} {\forall v_i \in V \ : \ \delta (G)=d(V_i)= \Delta (G)=2} {TEX}@@
---
!قضیه
در گراف ساده{TEX()} {G} {TEX}ثابت کنید{TEX()} {\sum_{v\in V(G)} d(v)=2\times |E|} {TEX}
یعنی مجموع درجات برابر است با دو برابر تعداد یالها
__اثبات__
تعداد یالها را به دو گونه می شماریم، یکی تعداد یالها یعنی {TEX()} {|E|} {TEX} بوده و دومی اینکه هر یالی ابتدا و انتها دارد که به ازای هر سر آن درجه یک راس را یک واحد افزایش داده، پس اگر مجموع تمام درجات رئوس را حساب کنیم هریال دقیقاً دو بار شمرده می شود و این یعنی دو برابر تعداد یالها می گردد. پس
@@{TEX()} {\sum_{v\in V(G)} d(v)=2\times |E|} {TEX}@@
---
!!نتیجه
مجموع درجات هر گراف{TEX()} {G} {TEX} زوج می باشد.
به وضوح از قضیه قبل نتیجه می گردد.
---
!قضیه
تعداد رئوس درجه فرد گراف {TEX()} {G} {TEX} ، زوج می باشد.
__برهان خلف__
اگر تعداد رئوس درجه فرد گراف {TEX()} {G} {TEX} فرد باشد،‌آنگاه مجموع درجات آنها عددی فرد می شود که با افزودن سایر درجه های زوج به عدد فرد باز هم مجموع درجات فرد باقی می ماند پس مجموع کل درجات گراف فرد می شود که مخالف با نتیجه قبل می باشد.
---
!تعریف. دنباله درجات رئوس
به دنباله ای که از پشت سر هم قرار دادن درجات رئوس گراف{TEX()} {G} {TEX} بدست می آید.
دنباله درجات رئوس گراف {TEX()} {G} {TEX} می گویند.
---
#@
@#16:
!!مثال
@@{TEX()} {(1,2,3,2,2)} {TEX}@@
ضمناً غالباً دنباله درجات رئوس را به ترتیب ((صعودی)) مرتب می کنند.
---
!تعریف. دنباله گرافیکی
به هر دنباله از ((اعداد طبیعی)) مانند{TEX()} {(a_1,a_2,\cdots ,a_n)} {TEX} که گرافی وجود داشته باشد که دنباله درجات رئوس آن برابر با این دنباله شود دنباله گرافیکی گویند مانند {TEX()} {(1,2,3,2,2)} {TEX} که در تمرین قبل دیدیم گرافی وجود دارد که دنباله درجات رئوس آن برابر با این دنباله شود.
حال سوالی که اینجا مطرح می شود این است که آیا هر دنباله اعدادی یک دنباله گرافیکی است؟
واضح است که خیر- پس چه دنباله اعدادی دنباله گرافیکی خواهند بود؟
نخست شروط لازم برای گرافیکی بودن دنباله را بررسی می کنیم.
1.در دنباله داده شده{TEX()} {0\le \delta (G) \le \Delta (G) <|V|} {TEX}.
!تمرین
آیا دنباله {TEX()} {(1,1,2,4)} {TEX}دنباله گرافیکی است.
__جواب__
خیر زیرا از تعداد اعداد معلوم است که گراف باید 4 راس داشته باشد ولی چون بزرگترین درجه آن 4 بوده و کوچکتر از تعداد رئوس نیست این دنباله گرافیکی نیست.
2.تعداد درجات فرد، زوج می باشد.
!تمرین
آیا دنباله{TEX()} {(1,1,1,2,3,3,4)} {TEX}می تواند گرافیکی باشد؟
__جواب__
خیر.
!تمرین
آیا گرافی وجود دارد که لااقل دو راس آن درجه {TEX()} {|V|-1} {TEX} باشد
__جواب__
به سادگی بلی، در گراف کامل{TEX()} {K_n} {TEX} درجه تمام رئوس{TEX()} {|V|-1} {TEX}می باشد.
---
!!مثال
#@
@#16:
یک شرط بازگشتی. فهرست 0،0،2 گرافیکی نیست، اما 1،2،2،1 گرافیکی است، همین طور 1،0،1 گراف {TEX()} {K_2+K_1} {TEX}، 1،0،1 را محقق می سازد؛ اگر راس جدیدی را مجاور با راس تنها و یک راس درجه 1 اضافه کنیم، آنگاه یک گراف با دنباله درجه های 1،1،2،2 به دست می آوریم ( تصویر زیر). برعکس، اگر یک گراف داشته باشیم 1،1،2،2 را محقق سازد و در آن راسی مانند{TEX()} {w} {TEX} از درجه ماکسیمم مجاور با راسهای از درجه 2 و 1 باشد،‌آنگاه می توانیم {TEX()} {w} {TEX} را برای به دست آوردن یک ((گراف)) با فهرست درجه های 1،0،1 حذف کنیم.
::{picture=img/daneshnameh_up/5/59/mco0050b.jpg}::
این ملاحظات یک آزمون بازگشتی را برای دنباله های گرافیکی ارائه می دهد. برای آزمون دنباله 33333221 ، می توانیم تحقق سازی را با راسی مانند {TEX()} {y} {TEX} از درجه 3 جستجو کنیم که دارای سه همسایه از درجه 3 باشد. چنین گرافی وجود دارد اگر، و فقط اگر،‌ 2223221 گرافیکی باشد ( به وسیله حذف‌‌ {TEX()} {y} {TEX} ). این را دوباره به صورت 3222221 مرتب می کنیم و تحقق سازی را با راسی مانند {TEX()} {x} {TEX} از درجه 3 جستجو می کنیم که دارای سه همسایه از درجه 2 باشد. چنین گرافی وجود دارد اگر، 111221 مرتب می کنیم و تحقق سازی را با راسی مانند {TEX()} {x} {TEX} از درجه 3 جستجو می کنیم که دارای سه همسایه از درجه 2 باشد. چنین گرافی وجود دارد اگر،‌ و فقط اگر،‌ 111221 گرافیکی باشد( به وسیله حذف {TEX()} {x} {TEX} ). این را دوباره به صورت 221111 مرتب می کنیم و تحقق سازی را با راسی مانند{TEX()} {w} {TEX} از درجه 2 با همسایه های درجه 2 و 1 جستجو می کنیم. چنین گرافی وجود دارد اگر و فقط اگر، 10111 گرافیکی باشد. شاید بتوان تشخیص داد که این واقعاً گرافیکی است. با آغاز یک تحقق سازی از 10111،‌می توانیم {TEX()} {y,x,w} {TEX} را با ویژگیهای مطلوب برای به دست آوردن یک تحقق سازی از دنباله اولیه 33333221 جایگزین کنیم. تحقق سازی یکتا نیست.
::{picture=img/daneshnameh_up/4/49/mco0050c.jpg}::
---
!قضیه. ( هاول1955 ، حکیمی 1962 )
برای {TEX()} {n>1} {TEX}، فهرست اعداد صحیح نامنفی{TEX()} {d} {TEX} با اندازه {TEX()} {n} {TEX}گرافیکی است اگر، و فقط اگر، {TEX()} {d^\prime} {TEX} گرافیکی باشد، در حالی که{TEX()} {d^\prime} {TEX} فهرستی با اندازه{TEX()} {n-1} {TEX} است که از {TEX()} {d} {TEX} با حذف بزرگترین عنصر آن {TEX()} {\Delta} {TEX} و کم کردن 1 از {TEX()} {\Delta} {TEX} بزرگترین عناصر بعدی به دست آمده است. تنها دنباله گرافیکی 1- عنصری، {TEX()} {d_1=0} {TEX}است.
__اثبات__
#@
@#16:
برای {TEX()} {n=1} {TEX}، گزاره بدیهی است. برای{TEX()} {n>1} {TEX}، نخست ثابت می کنیم که شرط کافی است. با در نظر گرفتن {TEX()} {d} {TEX} با قید {TEX()} {d_1\ge \cdots d_n} {TEX} ، و همچنین با در نظر گرفتن یک گراف ساده {TEX()} {G^\prime} {TEX} با دنباله درجه های {TEX()} {d^\prime} {TEX}، یک راس جدیدی مجاور با راسهای{TEX()} {G^\prime} {TEX} که دارای درجه های{TEX()} {d_{\Delta +1}-1,\cdots ,d_2-1} {TEX} است می افزاییم. این {TEX()} {d_i} {TEX} ها عبارتند از بزرگترین عناصر بعد از ( نسخه ای از ) {TEX()} {\Delta} {TEX} و خود، اما اعداد {TEX()} {d_{\Delta +1}-1,\cdots ,d_2-1} {TEX} لزومی ندارد که بزرگترین اعداد از{TEX()} {\Delta} {TEX} در{TEX()} {d^\prime} {TEX} باشند.
برای اثبات لزوم شرط، با یک گراف ساده {TEX()} {G} {TEX} که {TEX()} {d} {TEX} را محقق می سازد آغاز می کنیم و یک گراف ساده {TEX()} {G^\prime} {TEX} را ایجاد می کنیم که{TEX()} {d^\prime} {TEX} را محقق کند. فرض کنیم {TEX()} {w} {TEX} راسی از درجه {TEX()} {\Delta} {TEX} در {TEX()} {G} {TEX} باشد. فرض کنیم {TEX()} {S} {TEX} یک مجموعه از {TEX()} {\Delta} {TEX} راسهای در{TEX()} {G} {TEX} باشد که درای (( درجه های مطلوب )) {TEX()} {d_{\Delta +1},\cdots ,d_2} {TEX} است. اگر {TEX()} {N(w)=S} {TEX} ، آنگاه می توانیم با حذف{TEX()} {G^\prime ,w} {TEX} را به دست آوریم. در غیر این صورت، راسی از {TEX()} {S} {TEX} وجود دارد که از {TEX()} {N(w)} {TEX} حذف شده است. در این حالت،‌ {TEX()} {G} {TEX} را برای افزایش{TEX()} {|N(w)\cap S|} {TEX}بدون تغییر درجه هیچ راسی تعدیل می کنیم. چون{TEX()} {|N(w) \cap S|} {TEX} حداکثر {TEX()} {\Delta} {TEX} بار می تواند افزایش یابد،‌ تکرار این شیوه یک ((گراف)) دلخواه {TEX()} {G} {TEX} که {TEX()} {d} {TEX} را محقق می سازد به یک گراف {TEX()} {G^*} {TEX} تبدیل می کند که {TEX()} {d} {TEX} را محقق می نماید و دارای {TEX()} {N(w)=S} {TEX} است. حال از {TEX()} {G^*} {TEX} می توانیم {TEX()} {w} {TEX} را حذف کنیم تا گراف مطلوب {TEX()} {G^\prime} {TEX} را که {TEX()} {d^\prime} {TEX} را محقق می کند به دست می آوریم.
اگر{TEX()} {N(w)\neq S} {TEX}،‌ آنگاه می توانیم {TEX()} {z\notin S,x\in S} {TEX} را طوری انتخاب کنیم که{picture=img/daneshnameh_up/4/49/mco0050c.jpg}، زیرا {TEX()} {d(w)=\Delta=|S|} {TEX}. بنابر انتخاب {TEX()} {S} {TEX}، داریم {TEX()} {d(w) \ge d(z)} {TEX}. می خواهیم {TEX()} {wx} {TEX}را اضافه و{TEX()} {wz} {TEX}را حذف کنیم،‌ اما نباید درجه های راسها را تغییر دهیم،‌ بنابراین باید درجه های {TEX()} {z,x} {TEX} را دوباره بر قرار کنیم. کافی است راسی مانند {TEX()} {y} {TEX} را بیرون {TEX()} {T \{x,y,z \}} {TEX} طوری پیدا کنیم که{picture=img/daneshnameh_up/6/6b/mco0050e.jpg} ؛ اگر چنین {TEX()} {y} {TEX}ای وجود داشته باشد،‌ آنگاه همچنین می توانیم {TEX()} {xy} {TEX} را حذف و{TEX()} {zy} {TEX} را اضافه کنیم ( تصویر را ببیند ). فرض کنیم {TEX()} {\epsilon} {TEX} تعداد نسخه های یال {TEX()} {xz} {TEX} ( 0 یا 1‌ ) باشد. حال{TEX()} {x} {TEX} دارای{TEX()} {d(x)-\epsilon} {TEX} همسایه بیرون {TEX()} {T} {TEX} است،‌ و {TEX()} {z} {TEX} دارای {TEX()} {d(z)-1-\epsilon} {TEX} همسایه بیرون {TEX()} {T} {TEX} می باشد. چون{TEX()} {y,d(x) \ge d(z)} {TEX} مطلوب بیرون {TEX()} {T} {TEX} وجود دارد،‌ و می توانیم جابجایی مورد نظر را انجام می دهیم.
::{picture=img/daneshnameh_up/4/43/mco0050f.jpg}::
قضیه فوق فهرستی از {TEX()} {n} {TEX}عدد را با آزمودن فهرستی از {TEX()} {n-1} {TEX} عدد آزمون می کند؛ از این رو می توان آن را به عنوان یک الگوریتم تکراری برای آزمون اینکه آیا {TEX()} {d} {TEX} گرافیکی است انجام داد. شرط لازم ({TEX()} {\sum d_i} {TEX}زوج) به طور ضمنی در این مشخص سازی وجود دارد. چون{TEX()} {d^\prime , \sum d_i^{\prime }=\Big( \sum d_i \Big)-2\Delta} {TEX} باید دارای مجموع زوج برای تحقق پذیری باشد،‌ از این شرط بازگشتی ایجاب می کند که {TEX()} {d} {TEX} نیز باید مجموع زوج داشته باشد.
و در انتها تنها مطلبی که از مبحث درجه راسها باقی مانده و مهم است که اکنون تعریف شود اگر چه کاربرد آن در مباحث گرافهای جهت دار است عبارتست از:
---
!درجه ها در گرافهای جهت دار
نمادگذاری درجه راس برای گرافهای جهت دار وجه تمایز میان سرها و دمهای یالها را شامل می شود.
---
!تعریف
#@
@#16:
فرض کنیم {TEX()} {v} {TEX} راسی در یک گراف جهت دار باشد. درجه خروجی{TEX()} {d^+(v)} {TEX} تعداد یالهای با دم {TEX()} {v} {TEX} است. درجه ورودی {TEX()} {d^-(v)} {TEX} تعداد یالهای با سر {TEX()} {v} {TEX} است. همسایگی خروجی یا مجموعه تالی{TEX()} {N^+(v)} {TEX} عبارت است از{TEX()} {\{x\in V(G) \ : \ v \rightarrow x \}} {TEX}. همسایگی ورودی یا مجموعه مقدم{TEX()} {N^-(v)} {TEX} عبارت است از {TEX()} {\{x\in V(G) : x\rightarrow v \}} {TEX}.
برای گرافهای جهت دار دنباله ای از (( جفتهای درجه )) {TEX()} {\Big( d^+(v_i),d^-(v_i) \Big)} {TEX} را داریم. بسیاری از نتایج به دست آمده از گرافها شبیه نتایج حاصل از گرافهای جهت دار است. {TEX()} {2^{n\choose 2}} {TEX} گراف ساده با راسهای {TEX()} {v_n,\cdots v_1} {TEX} وجود دارند. به طور مشابهی،‌{TEX()} {2^{n^2}} {TEX} گراف جهت دار با این راسها وجود دارند به طوری که هر جفت مرتب حداکثر یک بار به عنوان یک یال ظاهر می شود. اگر وجود طوقه ها و داشتن هر دوی{TEX()} {y \rightarrow x,x\rightarrow y} {TEX} را منع کنیم،‌ آنگاه تنها{TEX()} {3^{n\choose 2}} {TEX} ((گراف جهت دار)) باقی می ماند؛ اینها با گرافهای ساده ارتباط نزدیکی دارند.
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0065.pdf]
---
!همچنین ببینید
*((گرافهای یکریخت ))
*((زیر گرافها ))
#@^