تحقیق درباره فرهنگ لغات نظریه گراف ها

لینک دانلود و خرید پایین توضیحات

فرمت فایل word  و قابل ویرایش و پرینت

تعداد صفحات: 11

فرهنگ لغات نظریه گراف ها

از wikipedia، دایره المعارف آزاد.

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

مندرجات

1-اصول ها

101-زیر مجموعة گراف ها

102-waiks

103-درفت ها

104-دسته ها

105-مولنه های متصل شدید

106-گره ها

107-جزئی ها

108-جایگزین ها

2-نزدیکی مجاورت و درجه

201-مستقل

3-اتصال

4-فاصله

5-نوع

6-گراف های وزنی و شبکه ها

7-سازماندهی

8-تنوع

9-ترکیب شده

10-رجوع کردن به

11- منابع

اصول ها

یک گراف G شامل دو عنصر به نام رئوس ها و لبه ها می شود. هر لبه ای، دو پایان در یک دسته اتوس دارد که به این دو نقطه پایانی اتصال یا الحاق گفته می شود همچنین یک دسته از لبه ها را می توان به عنوان یک زیر مجموعه از ترکیب دسته های دو عنصری رئوس ها تعریف نمود. بنابراین، دستة رئوس ها به عنوان یک دسته مورد بررسی قرار می گیرند و یک نسبت تلاقی وجود دارد که هر لبه ای را با یک جفت رئوس ترسیم می کنند که در اصل نقاط پایانی آن می باشد.

لبه ها ممکن است به سازمان عملی، راهنمایی نظریه ای از یک کران هدایت شده یا دو گرافی واگذار شده باشند، به بخش سازماندهی رجوع کنید.

مدل های جایگزین گراف موجود می باشد، برای مثال یک گراف ممکن است به عنوان یک تابع دو تائی بولی بیش از یک دسته رئوس یا به عنوان یک مجذور ماندیس (1/0) در نظر گرفته شده باشد.

یک رأس (عنصر اساس) معمولاٌ به عنوان یک گره یا یک نقطه ترسیم می شود. دست رأس از G معمولاٌ با علامت (G)Vیا با علامت V در زمان که هیچ بهم ریختگی مهمی وجود ندارد، مشخص می گردد. ترتیب یک گراف تعدادی از رئوس هایش با علامت

‍ می باشد.

یک لبه ای که (یک دسته از دو عنصرها)، به عنوان یک خط متصل به دو رأس، رئوس پایانی یا نقاط پایانی نامیده می شوند. یک لبه با رئوس پایانی x وy به وسیله xy علامت گذاری می شوند (بدون هر نشانه دیگری در میانشان). دسته لبه Gمعمولاٌ به وسیلة علامت (G)E، یا علامت E در زمانی که هیچ به هم ریختگی مهمی وجود ندارد، مشخص می گردد.

اندازة یک گراف، تعداد لبه های آن می باشد، مثال:

یک حلقه، لبه ای است و رئوس پایانی نیز رأس یکسان می باشد. فاصله رئوس پایانی یک دارد. اگر هر لبه ای با رئوس های یکسان وجود داشته باشد، یک لبه، گوناگون است در غیر اینصورت یک لبه به صورت ساده می باشد چندگانگی یک لبه، عداد لبه های گوناگون تقسیمی با رئوس های پایانی می باشد، چندگانگی از یک گراف، بیشترین چندگانگی از لبه هایش می باشد. اگر یک گراف هیچ لبه ها و حلقه های گوناگون نداشته باشد، یک گراف ساده محسوب می شود، اگر آن دارای لبه های گوناگون و بدون حلقه باشد، یک گراف گوناگون محسوب می شود و اگر آن شا مل حلقه ها و لبه های گوناگون (از تعداد بی فیل متناقض است) باشد، گراف چندگانه یا گراف ساختگی نام دارد. و گفته شد بدون هیچ قید و شرطی، یک گراف تقریباٌ همیشه ساده فرض می شود یا یک گراف از یک مشق گرفته می شود. برای لبه ها و رئوس یک گراف معمولاٌ به واگذاری برچسب های مشخص با نام برچسب زنی گراف رجوع می شود. گراف با لبه های برچسب دار و رئوس به عنوان برچسب دار و یا بدون آنها به عنوان عدم برچسب دار شده، شناخته می شود. به ویژه اینکه گراف ها با رئوس برچسب دار تنها، رأس برچسب شده می باشند و با لبه های برچسب دار، لبه برچسب شده. محسوب می گردد. (این کاربرد برای تشخیص گراف ها با رأس قابل شناس یا دسته های لبه از یک طرف و انواع هم ریختگی یا طبقه های گراف از طرف دیگر مورد استفاده قرار می گیرند) یک فرالبه ای لبه ای است که برای بردن هر تعداد از رئوس ها یا بیش از دو رأس اجازه یافته است یک گراف که هر فرالبه ای را می پذیرد، یک فراگرافی نامیده می شود. یک گراف ساده می تواند به عنوان یک مورد خاص فراگرافی به نام فراگرافی یکسان 2 مورد ملاحظه قرار گرفته باشد. بنابراین وقتی بدون شد، یک لبه همیشه شامل بیشترین رئوس دو فرقی می شود و یک گراف با یک فراگراف اشتباه می شود.

یک آنتی لبه، لبه ای است که آنبا وجود ندارد. با توضیح بیشتر اینکه، برای دور رئوس u و v، ‌} vوu ‍{، یک آنتی لبه در یک گراف G هر زمان که (VوU) یک لبه در G نباشد، وجود دارد. این بدان معنی ست که هیچ لبه ای به دو رئوس یا (برای گرافت های جهت دار) وجود ندارد و بیشترین لبه (UوV) از V به U وجود دارد.

یک آنتی سه گوش، یک دسته از سه رأس که متصل شده اند می باشد.

متمم G از یک گراف G، یک گراف با دسته رأس یکسان به عنوان G می باشد، اما با یک دسته لبه از قبیل XY ، یک لبه در G می باشد و تنها زمانی که XY در یک لبه در G نمی باشد.