سوال - کی می دونه این گراف ها چند یال و چند وجه دارند؟

[mf_5900]

سلام
از این که به این تاپیک سر زدید ممنون
می خواستم مشکل منو حل کنین
عنوان مساله :
می دانیم با تقسیم عدد به عوامل اولش می توان نمودار مقسوم علیه هایش را به صورت گراف ترسیم کرد
مثال :
3----- 6-------12
ا ا ا
ا ا ا
1------2--------4
حال طرح سوال:
می خوام بدونم آیا می توان فرمولی برای محاسبه ی تعداد یال ها و وجوه این نوع گراف ها (برای هر عددی که خواستیم با هر تعداد عوامل اول )پیدا کنیم.

کمک فوری

هر راهی که می شد فکر کردم حتی به توان عوامل اول فکر کردم ولی چیزی دستگیرم نشد
لطفا هر کی می دونه کمک کنه
ممنون

[davy jones]

سلام
از این که به این تاپیک سر زدید ممنون
می خواستم مشکل منو حل کنین
عنوان مساله :
می دانیم با تقسیم عدد به عوامل اولش می توان نمودار مقسوم علیه هایش را به صورت گراف ترسیم کرد
مثال :
3----- 6-------12
ا ا ا
ا ا ا
1------2--------4
حال طرح سوال:
می خوام بدونم آیا می توان فرمولی برای محاسبه ی تعداد یال ها و وجوه این نوع گراف ها (برای هر عددی که خواستیم با هر تعداد عوامل اول )پیدا کنیم.

کمک فوری

هر راهی که می شد فکر کردم حتی به توان عوامل اول فکر کردم ولی چیزی دستگیرم نشد
لطفا هر کی می دونه کمک کنه
ممنون

سلام.
هر مقسوم علیه عدد مرجع مورد نظر ما (که مثلا در مثال شما این عدد 12 است) میتونه به بعضی از مقسوم علیه های کوچکترمساوی با خودش یال داشته باشه. ولی مطمئنا به مقسوم علیه هایی که از خودش بزرگتر باشن نمیتونه یال داشته باشه. (مثلا 4 که مقسوم علیه 12 هستش میتونه به 2 یال داشته باشه ولی نمیتونه به 6 یال داشته باشه.) خیلی واضحه که هر عدد در این گراف به مجموعه ی مقسوم علیه های خودش یال خواهد داشت. (مثلا 12 به مجموعه ی مقسوم علیه های خودش که تعدادشون 6 تا هستش، 6 به مجموعه مقسوم علیه های خودش که 4 تا هستش و ... یال خواهد داشت)
بنابراین تعداد رئوس این گراف که برابر با تعداد مقسوم علیه های عدد مرجع هستش که این مقدار به سادگی قابل محاسبه هستش. برای بدست آوردن تعداد مقسوم علیه های یک عدد کافیه اون عدد رو به عوامل اولش تجزیه کنین و سپس توان هر عدد اول رو در تجزیه ی بدست اومده با یک جمع کنین و حاصل رو در هم ضرب کنین. مثلا برای تجزیه ی عدد 12 داریم:

که در اینجا به هر کدوم از توانهایی که با رنگ قرمز مشخص کردم، یک واحد اضافه میکنیم و در هر ضرب میکنیم:

3=1+2
2=1+1
تعداد مقسوم علیه ها = 2*3 = 6

بنابراین گراف متناظر با عدد 12، 6 تا راس داره.

حالا تو این گراف هر راس به راسی که مقسوم علیهش باشه یال داره. یعنی 12 به همه ی رئوس دیگه (و خودش) یال داره. راسی که عدد 6 رو نشون میده به چهار راس دیگه (تعداد مقسوم علیه های عدد 6، چهار تاست که خود عدد 6 رو هم شامل میشه) یال داره و همینطور تا آخر. روش محاسبه ی تعداد مقسوم علیه های هر راس هم مشابه محاسبه ی تعداد راسهای گراف هستش.

موفق باشین.
89/8/16