گراف چیست؟

[Rashowa]

در این تاپیک توضیحاتی کامل درباره گراف ها «گراف های سه تایی» داده می شود.
اگه غلط املایی یا نگارشی داشت دیگه ببخشید

متن مقاله:
گراف G يك سه تايي مرتب است كه تشكيل شده از يك مجموعه ناتهيV(G) از راس ها، يك مجموعه E(G) – مجزاي از V(G) – از يال ها و يك تابع وقوع كه به هر يال G ، يك زوج نا مرتب از راس هاي G را – كه الزاماً متمايز نيستند – نسبت مي دهد. اگر e يك يال وu و دو راس باشند به طوري كه ، در اين صورت گفته مي شود كه e، راس هايu و را به يكديگر وصل كرده است و راس هاي u و ، دو سر يال e ناميده مي شوند.
اگر يك گراف ، نموداري داشته باشد كه در آن يال ها تنها در راس هاي دو سر خود متقاطع باشند، مسطح ناميده مي شود چون مي توان به سادگي اين گونه گراف ها را روي يك صفحه مسطح رسم كرد
اگر مجموعه راس ها و مجموعه يال هاي يك گراف، متناهي باشند، گراف مزبور را متناهي مي نامند. گرافي را كه يك راس داشته باشد بديهي و ساير گراف ها را غير بديهي مي ناميم.
يك گراف ساده است، اگر هيچ طوقه اي نداشته باشد و بين هر دو راس آن ، بيش از يك يال نباشد . نمادهاي را به ترتيب براي نشان دادن تعداد راس ها و تعداد يال هاي گراف G به كار مي بريم.
متناظر با هر گراف G ، يك ماتريس وجود دارد كه ماتريس وقوع G ناميده مي‌شود. اگر راس هاي G را با و يال هاي آن را با نمايش دهيم، آنگاه ماتريس وقوع G ، ماتريسي مانند است كه در آن برابر با تعداد دفعاتي است (0،1 يا2) كه بر واقع شده است. در حقيقت ماتريس وقوع يك گراف ، طريقه ديگري يراي معين نمودن آن گراف است.
مي گوئيم گراف H، زير گراف G است (نوشته مي شود ) ، اگر از محدود كردن به E(H) حاصل شده باشد.
درجه راس در گراف ، برابر تعداد يال هاي واقع بر مي باشد. در اين تعريف ،هر طوقه به عنوان دو يال شمرده مي شود.
يك گشت از G دنباله نا صفر متناهي است به طوري كه جملات آن يك درميان از راس ها ويال ها بوده و به ازاي دو سر باشند. در اين صورت مي گوئيم w ، يك گشت از تا يا به عبارتي ديگر يك گشت است. راس هاي به ترتيب ابتدا و انتهاي w و راس هاي داخلي آن ناميده مي شود. همچنين عدد صحيح k را طول w مي ناميم.
اگر يال هاي در گذشت w متمايز باشند، w يك گذرگاه ناميده مي شود. در اين حالت ، طول w برابر با مي باشد. اگر علاوه بر يال ها ، راس هاي نيز متمايز باشند ، wيك مسير ناميده مي شود.
مي گوئيم دو راس uو از G همبند يا متصلند، اگر يك (,u ( مسير در G وجود داشته باشد . همبندي يك رابطه هم ارزي روي مجموعه راس هاي V تشكيل مي‌دهد. بنابراين افرازي از V به زير مجموعه هاي ناتهي وجود دارد كه در آن دو راس u و همبندند اگر و تنها اگر u و هر دو متعلق به مجموعه يكساني باشند.
مي گوئيم يك گشت ، بسته است ، اگر طول آن مثبت بوده ابتدا و انتهاي آن يكسان باشند. يك گذرگاه بسته كه ابتدا و راس هاي داخلي آن متمايز باشند، دور ناميده مي‌شود. همانند مسيرها، گاهي اوقات لفظ «دور» را به منظور اشاره به گرافي كه متناظر با يك دور است به كار مي بريم ، يك دور با طول kراk- دور مي ناميم.
يك k- دور بسته به اينكهk زوج يا فرد باشد ، يك دور زوج يا فرد مي ناميم. غالباً به 3- دور ، مثلث گفته مي شود.
يك گراف ، دو بخشي است اگر و تنها اگر هيچ دور فردي نداشته باشد.
گراف بي دور ، گرافي است كه هيچ دوري نداشته باشد. درخت يك گراف بي دور همبند است.

 

[mehran]

پاسخ : گراف چیست؟؟؟

واقعن نفهمیدم گراف چیست!
سطحش یه مقداری بالا بود!
نمی‌تونی در سطح خودمون (زیر دیپلم) توضیح بدی ببینیم چیه؟ اسمشو خیلی شنیدم!
به هر حال زحمت کشیدی، مرسی!

 

[Rashowa]

پاسخ : گراف چیست؟؟؟

واقعن نفهمیدم گراف چیست!
سطحش یه مقداری بالا بود!
نمی‌تونی در سطح خودمون (زیر دیپلم) توضیح بدی ببینیم چیه؟ اسمشو خیلی شنیدم!
به هر حال زحمت کشیدی، مرسی!

آره قبول دارم چون حتی خودمم درست و حسابی نفهمیدم «قدیم گفتن کسی که چیزی رو درست نفهمیده باشه نمی تونه درست آموزش بده»
حالا سعی می کنم اگه شد ساده تر توضیح بدم.
فعلا که نمی شه

 

[pico]

پاسخ : گراف چیست؟؟؟

آقا من هرچي فهميده بودم پريد ....
ولي مرسي ...

 

[Backstreetboy]

پاسخ : گراف چیست؟؟؟


نفهمیدم چی شد؟! :-[ :-\
ساده تر اگه شد بگید لطفا!

 

[parsa_spy]

پاسخ : گراف چیست؟؟؟

سادش این می شه :

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

این مقدمه گراف بود در حد زیر دیپلم !

 

[Backstreetboy]

پاسخ : گراف چیست؟؟؟

یه شکلی، عکسی، نموداری، چیزی اگه میشه بزنین تا به صورت شهودی گراف رو زیارت کنیم!

 

[s`dni]

پاسخ : گراف چیست؟؟؟

خوب گراف همین بود چه مسخره ! اونایی که در حد زیر دیپلم توضیح می دهند : بیششششششششششششششششششششتر

 

[pariya]

پاسخ : گراف چیست؟

حالا اصلا گراف به چه دردی میخوره؟؟؟؟!!!!

 

[mehran]

پاسخ : گراف چیست؟

خوب گراف همین بود چه مسخره ! اونایی که در حد زیر دیپلم توضیح می دهند : بیششششششششششششششششششششتر

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

به تعداد راس‌های گراف می‌گن مرتبه گراف و با p نشونش می‌دن ؛ به تعداد یال‌ها -یعنی همین خط‌هایی که راس‌ها رو به هم وصل می‌کنن- می‌گن اندازه‌ی گراف و با q نشون می‌دن.

شکل بالا، گرافی از مرتبه‌ی 6 و با 7 یال است.
اگه فقط از هر راس بشه که یک یال به راس دیگه کشید، به گراف می‌گن گراف ساده. گراف ساده‌ای رو هم که تمام یال های ممکنش کشیده شده باشن، می‌گن گراف کامل!
به تعداد یال‌هایی که از یه راس می‌گذرن می‌گیم درجه‌ی اون راس!
یه رابطه:
مجموع تمام درجه‌ها، برابر 2q ه.

اینم یه کم بیشتر!

یه شکلی، عکسی، نموداری، چیزی اگه میشه بزنین تا به صورت شهودی گراف رو زیارت کنیم!

عکس هم که هست!

حالا اصلا گراف به چه دردی میخوره؟؟؟؟!!!!

کاربردهای گراف خیلی زیاده.. خیلی خیلی!
امروز داشتم شیمی 2 می‌خوندم، دیدم ایزومرهای آلکان‌ها با درخت (که نوع خاصی از گراف‌ه) قابل رسم‌ه و اینجوری خیلی راحت‌تر می‌شه رسمشون کرد!
تا جایی که من می‌دونم، توی جاده کشی و معماری و تورهای توریسیتی و ... خیلی کاربرد داره.
نمونه‌ای از کاربردهاش:

 

[پگاه 1717]

پاسخ : گراف چیست؟

من در مورد گراف و بازی های ترکیبیاتی میتونم در حد زیر دیپلم بگم ولی مطمئن نیستم به این تاپیک ریط داشته باشه...

 

[mehran]

پاسخ : گراف چیست؟

من در مورد گراف و بازی های ترکیبیاتی میتونم در حد زیر دیپلم بگم ولی مطمئن نیستم به این تاپیک ریط داشته باشه...

حالا یه امتحانی بکن!
اگه ربط داشت چه بهتر، اگه نداشت لااقل اطلاعات ما بیش‌تر میشه!

 

[پگاه 1717]

پاسخ : گراف چیست؟

میشه به عنوان کاربرد گراف در نظر گرفت...

بازی های ترکیبیاتی ( توضیح این یکی دیگه واقعا ربطی نداره! ) رومیشه با گراف نشون داد. واسه اینکه بهتر بشه فهمید و حلشون کرد. وضعیت های بازی رو با راس ها نشون میدیم ، حرکت های بازی رو با یال ها.

برای گراف G هم میتونیم داشته باشیم : G=( X, E)

x
که X مجموعه راس هاست ، E مجموعه یال ها گفتیم راس ها یعنی وضعیت های بازی دیگه ،پس X مجموعه همه ی وضعیت های بازی هم هست.

حالا اگه واسه دو تا نقطه x و y داشته باشیم : x وy عضو X ( یعنی جزو راس ها باشن ) و ( x, y ) عضو E این معنی کلیش میشه که x به y وصل شده و به y میگیم تالی x.

یه چیز دیگه اینکه باری x و y که عضو X هستن اگه بتونیم با یه حرکت قانونی ( حرکت قانونی توی بازی ترکیبیاتی تعریف میشه ) از وضعیت x برسیم به وضعیت y داریم : (x , y ) عضو E

یه نکته دیگه اینکه اگه X متناهی باشه میگیم گراف G هم متناهیه.

دیگه... آهان ، مجموعه ی همه تالی های x رو با F(x) نشون میدیم. ( F ، تو پرانتز x ، اینجا بد نشون میده ) F(x) در واقع مجموعه همه ی وضعیت هاییه که بازیکن مجازه از وضعیت x به اونا حرکت کنه
اگه F(x) تهی باشه یعنی وضعیتی نیست که بازیکن بخواد از x به اون بره پس یعنی x میشه وضعیت پایانی. یعنی از x به هیچ جا نمیشه رفت.

( احساس میکنم خیلی بد دارم میگم )

تا اینجاشو فعلا داشته باشین...

( گشت و دور و اینا هم هست ، اونا فکر کنم بیشتر ربط داره... )

 

[monajem]

پاسخ : گراف چیست؟

احساس میکنم درست احساس کردی!

 

[پگاه 1717]

پاسخ : گراف چیست؟

احساس میکنم درست احساس کردی!

کجا هاشو نامفهموم گفته بودم؟

( با توجه یه اینکه من هنوز چیز خیلی خاصی نگفتما!)

 

[pariya]

پاسخ : گراف چیست؟

کجا هاشو نامفهموم گفته بودم؟

( با توجه یه اینکه من هنوز چیز خیلی خاصی نگفتما!)

یکم ساده تر توضیح بده (لطفا)

 

[پگاه 1717]

پاسخ : گراف چیست؟

من دارم نهایت تلاشمو میکنم که بد توضیح ندم

همون بالایی ها رو یه دور دیگه واضح تر میگم:

بازی های ترکیبیاتی یه سری بازی هستن که قوانین مربوز به خودشون و شیوه ی بازی خاص خودشون رو دارن نمونه اش این

این رو فقط گفتم که بدونیم بازی ترکیبیاتی یعنی چی

حالا ما واسه حل کردن این جور بازی ها میتونیم از رسم گراف استفاده کنیم که کار رو واسه مون راحت تر کنه. وقتی برای یه بازی گراف میکشیم ، وضعیت های بازی رو با راس ها و حرکت ها رو با یال ها نشون میدیم. ( توی اون بازی که لینک دادم وضعیت یعنی مثلا 7 تا مهره مونده بازیکن میخواد الان مهره برداره ، یعنی میخواد از یه وضعیت بره یه وضعیت دیگه )

خب ، یه گراف داریم اسموش میذاریم گراف G مجموعه راس های این گراف رو با X نشون میدیم ، مجموعه یال ها رو با E اینو اینطوری مینویسیم: G=(X,E)
x
گفتیم وضعیت های بازی رو با راس ها نشون میدیم الانم گفتیم مجموعه راس ها رو با X نشون میدیم ===> X میشه مجموعه وضعیت های بازی

اگه X متناهی باشه میگیم گراف G هم متناهیه

حالا دو تا نقطه داریم مثل a و b ( تو توضیح قبلی گفتم x و y ، حالا a و b میگم که با اون X قاطی نشه )

واسه این دو تا نقطه داریم : aوb عضو X و ( b و a ) عضو E

وقتی اینو میگن یعنی a و b دو تا راس گرافن که به هم وصلن. به b هم میگن تالی a

مجموعه تالی های a رو با F(a) نشون میدن.
این تیکه هم به نظرم زیاد نا مفهموم نبود دیگه:

" F(x) در واقع مجموعه همه ی وضعیت هاییه که بازیکن مجازه از وضعیت x به اونا حرکت کنه
اگه F(x) تهی باشه یعنی وضعیتی نیست که بازیکن بخواد از x به اون بره پس یعنی x میشه وضعیت پایانی. یعنی از x به هیچ جا نمیشه رفت."