• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

گراف چیست؟

  • شروع کننده موضوع
  • #1

Rashowa

کاربر فوق‌حرفه‌ای
ارسال‌ها
867
امتیاز
1,655
نام مرکز سمپاد
شهید بهشتی نیشابور
شهر
نیشابور
سال فارغ التحصیلی
1390
دانشگاه
علم و صنعت وArts et Métiers ParisTech
رشته دانشگاه
مهندسی صنایع
در این تاپیک توضیحاتی کامل درباره گراف ها «گراف های سه تایی» داده می شود.
اگه غلط املایی یا نگارشی داشت دیگه ببخشید :D

متن مقاله:
گراف 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

کاربر فوق‌حرفه‌ای
ارسال‌ها
732
امتیاز
1,087
نام مرکز سمپاد
شهید بهشتی
شهر
نیشابور
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : گراف چیست؟؟؟

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

Rashowa

کاربر فوق‌حرفه‌ای
ارسال‌ها
867
امتیاز
1,655
نام مرکز سمپاد
شهید بهشتی نیشابور
شهر
نیشابور
سال فارغ التحصیلی
1390
دانشگاه
علم و صنعت وArts et Métiers ParisTech
رشته دانشگاه
مهندسی صنایع
پاسخ : گراف چیست؟؟؟

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

pico

کاربر نیمه‌حرفه‌ای
ارسال‌ها
191
امتیاز
62
نام مرکز سمپاد
شهيد
شهر
سمنان
مدال المپیاد
المپياد فيزيك بسيج و غير بسيج
پاسخ : گراف چیست؟؟؟

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

Backstreetboy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,107
امتیاز
494
نام مرکز سمپاد
شهید بهشتی
رشته دانشگاه
مهندسی مکانیک
پاسخ : گراف چیست؟؟؟

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

parsa_spy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,161
امتیاز
441
نام مرکز سمپاد
علامه حلی تهران
شهر
تهران
سال فارغ التحصیلی
1390
مدال المپیاد
مدال طلای المپیاد کامپیوتر
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : گراف چیست؟؟؟

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

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

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

Backstreetboy

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,107
امتیاز
494
نام مرکز سمپاد
شهید بهشتی
رشته دانشگاه
مهندسی مکانیک
پاسخ : گراف چیست؟؟؟

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

s`dni

کاربر حرفه‌ای
ارسال‌ها
284
امتیاز
194
نام مرکز سمپاد
فرزانگان
شهر
سمنان
پاسخ : گراف چیست؟؟؟

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

pariya

کاربر فوق‌حرفه‌ای
ارسال‌ها
689
امتیاز
970
نام مرکز سمپاد
فرزانگان1
شهر
شیراز
مدال المپیاد
یه حماقتی کردیم یه زمانی :|
پاسخ : گراف چیست؟

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

mehran

کاربر فوق‌حرفه‌ای
ارسال‌ها
732
امتیاز
1,087
نام مرکز سمپاد
شهید بهشتی
شهر
نیشابور
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : گراف چیست؟

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

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

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

333px-6n-graf.svg.png

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

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


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


به نقل از pariya :
حالا اصلا گراف به چه دردی میخوره؟؟؟؟!!!!:D

کاربردهای گراف خیلی زیاده.. خیلی خیلی!
امروز داشتم شیمی 2 می‌خوندم، دیدم ایزومرهای آلکان‌ها با درخت (که نوع خاصی از گراف‌ه) قابل رسم‌ه و اینجوری خیلی راحت‌تر می‌شه رسمشون کرد!
تا جایی که من می‌دونم، توی جاده کشی و معماری و تورهای توریسیتی و ... خیلی کاربرد داره.
نمونه‌ای از کاربردهاش:
Konigsberg_bridges.png
 
ارسال‌ها
2,779
امتیاز
11,238
نام مرکز سمپاد
دبیرستان فرزانگان امین
شهر
اصفهان
مدال المپیاد
یه زمانی واسه شیمی/ نجوم میخوندم
پاسخ : گراف چیست؟

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

mehran

کاربر فوق‌حرفه‌ای
ارسال‌ها
732
امتیاز
1,087
نام مرکز سمپاد
شهید بهشتی
شهر
نیشابور
دانشگاه
صنعتی شریف
رشته دانشگاه
علوم کامپیوتر
پاسخ : گراف چیست؟

به نقل از peg0a2h1 :
من در مورد گراف و بازی های ترکیبیاتی میتونم در حد زیر دیپلم بگم ولی مطمئن نیستم به این تاپیک ریط داشته باشه...
حالا یه امتحانی بکن! :D
اگه ربط داشت چه بهتر، اگه نداشت لااقل اطلاعات ما بیش‌تر میشه! :D
 
ارسال‌ها
2,779
امتیاز
11,238
نام مرکز سمپاد
دبیرستان فرزانگان امین
شهر
اصفهان
مدال المپیاد
یه زمانی واسه شیمی/ نجوم میخوندم
پاسخ : گراف چیست؟

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

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

برای گراف 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 ، اینجا بد نشون میده :D ) F(x) در واقع مجموعه همه ی وضعیت هاییه که بازیکن مجازه از وضعیت x به اونا حرکت کنه
اگه F(x) تهی باشه یعنی وضعیتی نیست که بازیکن بخواد از x به اون بره پس یعنی x میشه وضعیت پایانی. یعنی از x به هیچ جا نمیشه رفت.

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

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

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

monajem

کاربر فوق‌حرفه‌ای
ارسال‌ها
933
امتیاز
0
نام مرکز سمپاد
علامه حلی اراک
شهر
اراک
مدال المپیاد
کامپیوتر-طلا
دانشگاه
صنعتی شریف
رشته دانشگاه
نرم افزار
پاسخ : گراف چیست؟

احساس میکنم درست احساس کردی!
 
ارسال‌ها
2,779
امتیاز
11,238
نام مرکز سمپاد
دبیرستان فرزانگان امین
شهر
اصفهان
مدال المپیاد
یه زمانی واسه شیمی/ نجوم میخوندم
پاسخ : گراف چیست؟

به نقل از منجم! :
احساس میکنم درست احساس کردی!

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

pariya

کاربر فوق‌حرفه‌ای
ارسال‌ها
689
امتیاز
970
نام مرکز سمپاد
فرزانگان1
شهر
شیراز
مدال المپیاد
یه حماقتی کردیم یه زمانی :|
پاسخ : گراف چیست؟

به نقل از peg0a2h1 :
کجا هاشو نامفهموم گفته بودم؟
:D
( با توجه یه اینکه من هنوز چیز خیلی خاصی نگفتما!)
یکم ساده تر توضیح بده (لطفا)
 
ارسال‌ها
2,779
امتیاز
11,238
نام مرکز سمپاد
دبیرستان فرزانگان امین
شهر
اصفهان
مدال المپیاد
یه زمانی واسه شیمی/ نجوم میخوندم
پاسخ : گراف چیست؟

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

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

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

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

حالا ما واسه حل کردن این جور بازی ها میتونیم از رسم گراف استفاده کنیم که کار رو واسه مون راحت تر کنه. وقتی برای یه بازی گراف میکشیم ، وضعیت های بازی رو با راس ها و حرکت ها رو با یال ها نشون میدیم. ( توی اون بازی که لینک دادم وضعیت یعنی مثلا 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) نشون میدن.
این تیکه هم به نظرم زیاد نا مفهموم نبود دیگه: :D

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