جبر مجرّد (به انگلیسی: Abstract algebra) شاخهایست از ریاضیات که به بررسی ساختارهای جبری مثل گروه، حلقه، و میدان میپردازد. آغاز تعریف رسمی این گونه ساختارها به قرن نوزدهم (م) باز میگردد.
اصطلاح «جبر مجرّد» در برابر «جبر مقدّماتی» یا «جبر دبیرستانی» بهکار میرود. در حدود نیمه اوّل قرن بیستم این رشته را «جبر مدرن» مینامیدند.
جبر مجرد مقدماتی، اشیاء و اعمال ریاضی را، فارغ از ماهیت آنها بررسی میکند. اعداد، توابع، ماتریسها، از عناصر آن و اعمال دوتایی ضرب، ترکیب توابع و... از اعمال آن به شمار میآیند. دسته بندی گروهها و حلقهها از موضوعات اساسی این شاخه به حساب میآیند. برخی شاخههای هندسی با جبر مجرد ارتباط پیدا میکنند.
جبر مقدماتی بهمراه جبر مجرد و جبر خطی سه شاخهٔ اصلی دستگاه جبر را تشکیل میدهند.
نظریه اعداد شاخهای از ریاضیات محض است که در مورد خواص اعداد صحیح بحث میکند.
نظریه مقدماتی اعداد:
در نظریه مقدماتی اعداد، اعداد صحیح را بی استفاده از روشهای بهکار رفته در سایر شاخههای ریاضی بررسی میکنند. مسائل بخش پذیری، الگوریتم اقلیدس برای محاسبه بزرگترین مقسومعلیه مشترک (ب.م.م)، تجزیه اعداد به اعداد اول، جستجوی عدد تام perfect number و همنهشتیها در این رده هستند. برخی از یافتههای مهم این رشته قضیه کوچک فرما، قضیه اعداد اول و قضیه اویلر، قضیه باقیمانده چینی و قانون تقابل درجه دوم هستند. خواص توابع ضربی مانند تابع موبیوس و تابع φ اویلر و دنباله اعداد صحیح و فاکتوریلها و اعداد فیبوناچی در همین حوزه قرار دارند.
حل بسیاری از مسائل در نظریه مقدماتی اعداد بر خلاف ظاهر ساده آنها نیازمند کوشش بسیار و بهکار گرفتن روشهای نوین است. چند نمونه:
- حدس گلدباخ در مورد نمایش اعداد زوج به صورت جمع دو عدد اول،
- حدس کاتالان در مورد توانهای متوالی از اعداد صحیح،
- حدس اعداد اول تؤامان در مورد بینهایت بودن زوجهای اعداد اول،
- حدس کولاتز در مورد تکرار ساده،
- حدس اعداد اول مرسن در مورد بینهایت بودن اعداد اول مرسن و ...
همچنین ثابت شده که نظریه معادلات دیوفانتی تصمیمناپذیر است (به مسئله دهم هیلبرت مراجعه کنید).
نظریه تحلیلی اعداد:
در نظریه تحلیلی اعداد از حسابان و آنالیز مختلط برای بررسی سؤالاتی در مورد اعداد صحیح استفاه میشود. مثالهایی در این مورد قضیه اعداد اول و فرض ریمان هستند. مسئله وارینگ (یعنی نمایش هر عدد صحیح به صورت جمع چند مربع یا مکعب)، حدس اعداد اول تؤامان (یافتن بینهایت عدد اول با اختلاف ۲)، و حدس گلدباخ (نمایش هر عدد زوج بهصورت مجموع دو عدد اول) نیز با روشهای تحلیلی مورد حمله قرار گرفتهاند. اثبات متعالی (ترافرازنده) بودن ثابتهای ریاضی مانند
و
e نیز در بخش نظریه تحلیلی اعداد قرار دارند. اگرچه حکمهایی در مورد اعداد ترافرازنده خارج از محدوده مطالعات اعداد صحیح به نظر میآید، در واقع مقادیر ممکن برای چند جملهایها با ضریبهای صحیح مانند
e را بررسی میکنند. همچنین اینگونه مسائل با مبحث تقریب دیوفانتین نیز ارتباط نزدیک دارند که موضوع آن این است که چگونه میتوان یک عدد حقیقی داده شده را با یک عدد گویا تقریب زد؟
نظریه جبری اعداد:
در نظریه جبری اعداد، مفهوم عدد به اعداد جبری، که همان ریشههای چند جملهایهائی با ضریب گویا هستند، گسترش مییابد. در این حوزه اعدادی مشابه اعداد صحیح با نام اعداد صحیح جبری وجود دارد. در این عرصه لازم نیست ویژگیهای آشنای اعداد صحیح (مانند تجزیه یگانه) برقرار باشد. مزیت روشهای استفاده شده در این رشته (مثل نظریه گالوا، میدان همانستگی field cohomology، نظریه رده میدان class field theory، نمایشهای گروهها و توابع-L) این است که برای این رده از اعداد، نظم را تا حدودی تأمین مکند.
حمله به بسیاری از سؤالات نظریه اعداد به صورت «پیمانه p، برای کلیه اعداد اول p» مناسبتر است (به میدانهای متناهی مراحعه کنید). به چنین کاری «محلی سازی» میگویند که به ساختن عدد p-ای میانجامد. نام این رشته «تحلیل موضعی» است که از نظریه اعداد جبری ناشی میشود.
نظریه ترکیبیاتی اعداد:
نظریه ترکیبیاتی اعداد به مسائلی در نظریه اعداد میپردازد که با روشهای ترکیبیاتی بررسی میشوند. پل اردوش بنیانگذار اصلی این شاخه از نظریه اعداد بود.
نظریه محاسباتی اعداد:
نظریه محاسباتی اعداد به الگوریتمهای مربوط به نظریه اعداد میپردازد. الگوریتمهای سریع برای امتحان اعداد اول و تجزیه اعداد صحیح در رمزنگاری کاربردهای مهمی دارند.
هندسه جبری شاخهای از ریاضیات است که مفاهیم جبر مجرد، به ویژه جبر جابجایی، را با مسائل هندسه میآمیزد. این شاخه از ریاضیات مدرن با آنالیز مختلط، توپولوژی و نظریه اعداد در ارتباط تنگاتنگ است. واریته آفین n-بعدی که یکی از بنیادی ترین مفاهیم این شاخه از ریاضی است دقیقا صفرهای مشترک تعدادی دلخواه از چند جمله ای های n-متغیره روی میدان مفروض تعریف می شود. بنابراین حلقه ی چند جمله ای ها نقش عمده ای در هندسه جبری ایفا می کند. تاریخ این علم گسترش فروانی دارد، طوری که قسمتی از مطالعات ارشمیدس مسائلی پیرامون مقاطع مخروطی، تشکیل می داد. همچنین فیزیک دان مسلمان ایرانی قرن ۱۰ میلادی ابن هیثم برای محاسبه ی مسافت ها مجبور به استفاده از معادلات درجه ی سوم می شده است. و نهایت اینکه خیام معادله ی درجه ی سوم را در کلی ترین حالت حل نمود. وی این کار را از طریق مقاطع مخروطی، و قطع دادن دایره با سهمی درجه دوم، انجام داد.
نظریه گروهها:
گروه از جمله مهمترین ساختارهای جبری است که نقش اساسی در جبر مجرد دارد و در علوم مختلف مانند بلور شناسی، فیزیک، کوانتم و... از اهمیت بالایی برخوردار است.
فکر تشکیل نظریه گروهها زمانی شکل گرفت که ریاضیدانان مشاهده کردند ساختارهایی را که مطالعه میکنند در خواصی مشترک هستند و اگر بتوانند همه این خواص را در مورد یک ساختار مشخص بررسی کنند در حقیقت بخش وسیعی از ساختارهای مشابه را مطالعه کردهاند و به این ترتیب در زمان صرفه جویی میشود.
شاخهای از ریاضیات را که به مطالعه گروهها اختصاص دارد
نظریه گروهها نامیده میشود.
مرور تاریخی:
نظریه گروهها بهوسیله چهارشاخه عمده از ریاضیات جبر کلاسیک، نظریه اعداد، هندسه و آنالیز رشد و گسترش یافت. جبر کلاسیک در سال 1770 با کارهای ژوزف لویی لاگرانژ برروی معادلات چندجملهای پایه گذاری شد.
نظریه اعداد بهوسیله کارل فردریش گاوس در سال 1801 مورد مطالعه و گسترش هرچه بیشتر قرار گرفت و سی.اف.کلاین در زمینه هندسه و ارتباط تبدیلات هندسی و گروهها کارهای بسیار انجام دادهاست به طوری که او را پدر این بخش از نظریه گروهها میدانند و بنیانگذار شاخه آنالیز نیز هنری پوانکاره، اس.لی لای و سی.اف کلاین هستند.
اما اویلر(Euler)، گاوس(Gauss)، لاگرانژ(Lagrange)، آبل(Abel) و ریاضیدان فرانسوی گالوا(Galois) اولین کسانی بودند که در زمینه نظریه گروهها به تحقیق پرداخته بودند. خصوصاً گالوا بدلیل قضیه اساسی خود که رابطی بین گروهها و حلقهها است و امروزه آن را قضیه گالوا میخوانند بسیار مورد توجه است.
اگرچه مفهوم گروه تبدیلها در مطالعه هندسه به کندی صورت گرفته است، اما کار اصلی در گسترش مفهوم گروه از مطالعه معادلات چندجملهای حاصل شده است. یونانیان قدیم از روشهای حل معادله درجه دو آگاه بودند. در قرن شانزدهم قدمهایی برای حل معادلات درجه سوم و چهارم روی Q برداشته شد. اولین کاربرد گروهها در توصیف تأثیر جایگشتهای ریشههای یک معادله چند جملهای بودهاست که بهوسیله لاگرانژ مورد استفاده قرار گرفتهاست که بر مبنای همین او توانست نظریه جانشانی را سازمان دهد.
او کشف کرد که ریشههای همه مواردی را که او امتحان کردهاست توابعی گویا از ریشههای معادلات متناظرشان هستند. لئونارد اویلر(1707-1783) و ژوزف لویی لاگرانژ(1736-1813) هر دو، با ادامه کار با چند جمله ایهای درجه پجم و بالاتر سعی کردند معادله درجه پنجم کلی را حل کنند. لاگرانژ دریافته بود که بین درجه n معادله چند جملهای و گروه جایگشتی Sn باید رابطهای وجود داشته باشد. پس از او رافینی در تلاش برای اثبات عدم وجود راه حل مستقیم برای حل معادلات درجه پنجم و بالاتر گامهای دیگری را در زمینه نظریه گروهها برداشت.
اما این نیلس هنریک آبل(1802-1829) بود که سرانجام ثابت کرد پیدا کردن فرمولی برای حل معادله درجه پنجم کلی، تنها با جمع و تفریق و ضرب و تقسیم و ریشه گیری ممکن نیست.
در طی همین دوران، اواریست گالوا (1811-1832) ریاضیدان معروف فرانسوی وجود شرط لازم و کافی برای حل چند جملهای درجه پپنجم یا بالاتر با ضرایب گویا، به وسیله رادیکالها را تحقیق کرد. در کار گالوا ساختارهای گروهی و هیاتها به کار میروند.گالوا نخستین اثر خود را در مورد نظریه گروهها در سن 18 سالگی(1829)منتشر ساخت. اما کمکهای او تا قبل از انتشار مجموعه مقالاتش در سال 1846 مورد توجه قرار نگرفت.
به دنبال دستاوردهای گالوا، نظریه گروهها جای خود را در بسیاری از زمینههای ریاضی باز کرد. مثلا، ریاضی دان آلمانی فلیکس کلاین (1849-1929) در آنچه که به برنامه ارلانگر معروف است، سعی کرد که تمام هندسههای موجود را بر حسب گروه تبدیلهایی که تحت آنها ویژگیهای هندسه ناوردا بودند تدوین کند.
بعد از او آرتور کیلی و آگوستین لویی کوشی به اهمیت کارهای گالوا پی بردند و به تحقیقات بیشتر در این زمینه پرداختند. از جمله ریاضیدانانی که در قرن نوزدهم در زمینه نظریه گروهها کار میکردند میتوان برتراند، چارلز هرمیت، فروبنیوس و لئوپارد کرونکر و امیل ماتیو را نام برد.
تا آن زمان اصول موضوع معینی برای تعریف گروه وجود نداشت. در سال 1854 کیلی اولین اصول موضوع را برای گروهها ارائه داد اما تعریف وی به زودی فاقد ارزش شد. در سال 1870، کرونکر مجدداً اصول موضوعی را برای گروهها پایه گذاشت. همچنین اچ.وبر در سال 1882، تعریفی برای گروههای متناهی و در سال 1883 تعریفی برای گروههای نامتناهی انجام داد.
والتر فون دایک در سال 1882 اولین تعریف مدرن از گروه را ارائه داد.
مطالعه گروههای لای و زیرگروههای گسسته شان و گروههای تبدیلی در سال 1884 به طور منظم توسط سوفوس لای شورع شد.
در طی قرن بیستم پژوهشهای بسیار زیادی برای تحلیل ساختار گروههای متناهی صورت گرفت. در دهههای اخیر، ریاضیدانان در جست و جوی همه گروههای ساده متناهی و توضیح نقش آنها در ساختار تمام گروههای متناهی بودهاند. از جمله پشگامان این بسط، والترفیت، جان تامسن، دانیل گورنشتین، میشاییل آشباخر و رابرت گریس هستند.
امروزه نظریه گروهها به بنیادیترین نظریهها در جبر مجرد تبدیل شدهاست و منبع تحقیقات فراوانی برای ریاضیدانان است.
گروه ها:
ابتدا یادآوری میکنیم که یک ساختمان جبری عبارت است از یک مجموعه به همراه یک یا چند عمل دوتایی و رابطه که روی آن مجموعه تعریف شدهاست. گروه نیز از جمله ساختمانهای جبری است.
گروه یک ساختار جبری بر روی یک گروه ناتهی است که نسبت به یک عمل دوتایی بسته باشد و نسبت به آن عمل دارای خاصیت شرکت پذیری باشد. هم چنین وجود عنصر همانی و عنصر عکس در این ساختار الزامیست. به موجب این تعریف:
اگر G مجموعه ناتهی و ο عملی دوتایی روی G باشد، آنگاه (G,ο) را یک گروه مینامیم اگر شرایط زیر برقرار باشد:
- برای هر a ο b ∈ G، a,b ∈ G. (بسته بودن G نسبت به عمل ο)
- برای هر a ο (b ο c) = (a ο b) ο c ، a,b,c ∈ G. (ویژگی شرکت پذیری)
- برای هر a ∈ G، یک e∈G وجود دارد که a ο e = e ο a = a. (وجود عنصر همانی)
- برای هر a ∈ G، یک b∈G وجود دارد که a ο b = b ο a = e. (وجود عنصر عکس)
گروهها را میتوان بسته به ویژگیهای آن دستهبندی کرد:
گروه دوری
گروه G را دوری میخوانند اگر یک عنصر x ∈ G وجود داشته باشد به قسمی که برای هر a ∈ G، برای مقداری از n متعلق به Z، داشته باشیم: a = xn
مفهوم گروه دوری به مفهوم وابستهای منجر میشود. فرض کنید گروه G را داریم، اگر a ∈ G، مجموعه S= {an>|k∈Z}۰ را در نظر میگیریم. از مطالب ذکر شده به عنوان قضیه میتوان به این نتیجه رسید که S زیر گروه G است. این زیر گروه را زیر گروه تولید شده به وسیله a مینامند و با <a> نمایش میدهند.
در این جا تعداد اعضای S را مرتبه a مینامند و با σ(a)۰ نمایش میدهند که در واقع |<a>| میباشد. در صورتی که |<a>| نامتناهی باشد میگوییم که a مرتبه نامتناهی دارد.
در این جا قضایای تعیین کننده روابط بین گروه و زیرگروههای آنها را بیان میکنیم.
- فرض کنید a ∈ G و & sigma;(a) = n. اگر k ∈ Z و ak = e آنگاه n|k.
- درصورتی که G یک گروه دوری باشد.
- اگر G متناهی باشد، آنگاه با (+,Z) یکریخت است.
- اگر مرتبه G برابر با n باشد، آنگاه با (+,Zn) یکریخت است.
- هر زیرگروه یک گروه دوری، گروهی دوری است.
- گروه جایگشتی
گروه جایگشتی
گروه متناهی
گروه متناهی گروهی است که به مرتبه آن(به مرتبه گروه در همین مقاله مراجعه کنید)نتوان عددی نسبت داد.(تعداد اعضا محدود نباشند)
گروه آبلی
گروه آبلی یا تعویض پدیر گروهی است که علاوه بر خصوصیتهای بالا، تعویض پذیر نیز باشد. صفت آبلی به افتخار ریاضیدان نروژِی، نیلس هنریک آبل اختیار شدهاست. برای هر a,b ∈ G، داریم a ο b = b ο a
گروه آبلی متناهی
گروههای آبلی متناهی، گروهی است که علاوه بر مرتبه متناهی دارای خاصیت جابجایی در عمل بین اعضای خود باشد.
گروه خارج قسمتی
گروه دووجهی
اصطلاحات موجود در نظریه گروهها عمل دوتایی - گروه آبلی - زیرگروه - مرکز گروه - هم مجموعهها - مرکز ساز گروه - نرمال ساز گروه - زیرگروه نرمال - مرتبه گروه - مرتبه عضو - گروه دوری - گروه خارج قسمت - گروه متقارن - همومورفیسم - قضایای ایزومورفیسم - حاصل ضرب مستقیم - تزویج - معادله کلاسی - قضیه کیلی - قضیه لاگرانژ - قضیه کوشی - قضایای سیلو
تعاریف و ویژگیهای مقدماتی
در صورتی که برای عمل گروه نشانهای در نظر نگیریم به صورت پیش فرض ضربی خواهد بود.
توان در گروههای ضربی
برای هر عنصر توان را به صورت زیر تعریف میکنیم:
a0 = e.
n ≥0، an+1 = an .a
از طرف دیگر چون هر عنصر گروه عکسی دارد، باید a-n در نظر گرفته شود، برای n ∈ Z+ تعریف میکنیم:
همچنین برای am.an = am+nm,n∈ Z وam)n = amn) میباشند.(در مورد گروه با عمل با خواص جمعی خواص متناظر با این موارد مشاهده میشود.)
مرتبه گروه وقتی G گروه نامتناهی است، تعداد عنصرهای آن را مرتبه G مینامند و با |G| نمایش میدهند. مثلا برای Zn,+)| = n ،n ∈ Z+v)| و برای هر عدد اول p، داریم : Zp*,.)| = p-1)|
زیرگروه
زیرمجموعه ناتهی H از گروه G را زیرگروه G میگوییم هرگاه H تحت عمل گروه G تشکیل یک گروه بدهد. اگر H زیرگروه G باشد مینویسیم H⊆G.
توجه داشته باشید که از آن جا که H خود یک گروهاست، سایر خواص یک گروه را داراست.
قضایای مقدماتی
- برای هر گروه G
- عنصر همانی G یکتاست.
- عکس هر عنصر G یکتاست.
- اگر ac = ab ، a,b,c ∈ G در این صورت b = c.(حذف از چپ)
- اگر ca = ba ، a,b,c ∈ G در این صورت b = c.(حذف از راست)
- برای هر ab)2 = b2a2 ، a,b ∈ G) اگر و تنها اگر گروه G آبلی باشد.
- اگر H زیرمجموعهای ناتهی از گروه G باشد، H زیرگروه G است اگر و فقط اگر:
- H تحت عمل G بسته باشد یعنی برای هر a,b∈H داشته باشیم ab∈H
- H تحت معکوس هر عضو بسته باشد، یعنی اگر a∈H آنگاه a-1∈H
- شرط تناهی این وضعیت را بهتر میکند:
اگر G گروه باشد و π ≠ H ⊆ G و H متناهی باشد، آن گاه H زیرگروه G است اگر و تنها اگر H تحت عمل دودوی G بسته باشد.
- فرض کنید (G,ο) و (*,H) دو گروه باشند. عمل دوتایی . را بر G×H به نحو زیر تعریف میکنیم:
(g۱,h۱).(g۲,h۲) = ( g۱οg۲,h۱*h۲) در این صورت، (.,G×H) یک گروهاست و حاصل ضرب مستقیم G و H خوانده میشود.
هم ریختیها و یک ریختی ها
در صورتی که (G,ο) و (*,H) دو گروه باشند و f:G→H، در صورتی که برای هر a,b ∈ G داشته باشیم: f(aοb) = f(a)*f(b)۰ آنگاه f را هم ریختی گروهی مینامند. اگر بدانیم که ساختارهای داده شده گروه هستند f را فقط همریختی میخوانیم.
- فرض کنید (G,ο) و (*,H) گروههایی به ترتیب با عناصر همانی eG و eH باشند، اگر f:G→H در این صورت:
- f(eG) = eH
- برای هر a ∈G ، f(a-۱) = [f(a)]-۱
- برای هر a ∈G و هر n ∈Z ، f(an) = [f(a)]n
- برای هر زیر گروه S از f(S)، G زیر گروه Hاست.
اگر f:(G,ο) &→ (H,*)۰ یک همریختی باشد، f را یک یکریختی مینامند اگر و تنها اگر f یک به یک و پوشا باشد. در این حالت میگویند G و H گروههای یکریختن اند.
هم مجموعه ها
هم مجموعهها در نظریه گروهها، از مفاهیم اساسی برای تعریف گروه خارج قسمت هستد و در سراسر نظریه گروهها به آنها بر خورد میکنیم. در صورتی که H زیر گروه G باشد، آنگاه برای هر a ∈ G مجموعه aH={ah|h ∈ H}۰ را هم مجموعه چپ H در G مینامند. مجموعه Ha={ha|h ∈ H}۰ هم مچموعه راست H در G است. (به همین ترتیب در صورتی که عمل گروه دارای خواص جمعی باشد مجموعههای H+a={h+a|h ∈ H}۰ و a+H={a+h|h ∈ H}۰ هم مجموعههای چپ و راست خواهند بود.)
- اگر H زیر گروهی از گروه متناهی G باشد، آنگاه برای هر a,b ∈ H داریم:
- |aH| = |H|
- aH = bH یا aH ∩ bH = Φ
از کاربردهای اولیه هم مجموعهها در اثبات قضایایی نظیر قضیه لاگرانژ است که جلوتر به آن اشاره میشود.
قضایای پیشرفته در نظریه گروه ها:
قضیه لاگرانژ
قضیه لاگرانژ بیان میکند که اگر G یک گروه متناهی و H زیرگروه G باشد، مرتبه H مرتبه G را عاد میکند. قضیه لاگرانژ با استفاده از مفهوم هم مجموعهها به راحتی قابل استفادهاست. فرعهای زیر از قضیه لاگرانژ قابل استنباط هستند:
- اگر G گروهی متناهی باشد، و a ∈ G، آنگاه |o(a)| |G.
- هر گروهی که مرتبه آن یک عدد اول باشد، گروهی دوری است.
- اگر G گروهی متناهی از مرتبه n باشد و x∈G آنگاه xn=e.
برای اثبات این مطلب زیرگروه دوری تولید شده توسط x یعنی <x> را در نظر میگیریم. فرض میکنیم <x> از مرتبه m باشد. در این صورت قضیه لاگرانژ ایجاب میکند که m|n پس عدد صحیح k وجود دارد که n=mk.
از طرفی m مرتبه عضو(کوچکترین عدد صحیح مثبت که اگر x به توان آن برسد حاصل عضو خنثی گروه G شود) x است پس xm=e
بنابراین:
این نتیجه علاوه بر کاربردهایش در مورد گروهها، برای ارائه برهانی جبری برای قضیه کوچک فرما و قضیه اویلر استفاده میشود.
قضیه پوانکاره:
قضیه پوانکاره بیان میکند که اگر G یک گروه باشد و K,H زیرگروههای G با اندیس متناهی در G باشند،
قضیه کیلی
قضیه کیلی بیان میکند که هر گروه G با زیرمجموعهای از گروه متقارن روی G ایزومورف است.
قضایای سیلو
قضیه برنساید
لم برنساید
لم برنساید روشی را بیان میکند برای شمارش افرازهای یک مجموعه به وسیله یک گروه از تبدیلات برای اطلاعات بیشتر میتوانید به صفحه مربوطه مراجعه کنید.
قضایای ایزومورفیسم
لم جوردن-هولدر
نمونههایی از گروههای مهم مثالهای زیادی از گروهها وجود دارد. یه عنوان مثال مجموعه اعداد صحیح به همراه عمل جمع یک گروهاست که آبلی نیز میباشد. در این قسمت چند نمونه از گروهها را که معمولاً در بررسیها مورد استفاده قرار میگیرند را معرفی میکنیم. خواننده میتواند گروه بودن هر نمونه را بررسی کند.
فرض کنید {V={a,b,c,d یک مجموعه چهارعضوی باشد. عمل * را روی V به صورت زیر تعریف میکنیم:
* |
a |
b |
c |
d |
a |
a |
b |
c |
d |
b |
b |
a |
d |
c |
c |
c |
d |
a |
b |
d |
d |
c |
b |
a |
در این صورت V گروهی آبلی و متناهی به نام گروه چهارتایی کلاین تشکیل میدهد.(گروه کلاین مربوط به تقارنهای مستطیل میباشد)
میدانید اگر m عددی طبیعی باشد، رابطه همنهشتی به هنگ m یا یک رابطه هم ارزی روی مجموعه اعداد صحیح
تعریف میکند که مجموعه خارج قسمت آن (مجموعه همه کلاسهای هم ارزی رابطه هم ارزی) را با نشان میدهیم.
اگر برای هر عدد صحیح a کلاس هم ارزی a را با نشان دهیم، در این صورت:
حال عمل ⊕ موسوم به جمع نیمی یا جمع با پیمانه m را به صورت
تعریف میکنیم. در این صورت خواننده آشنا با نظریه همنهشتی به سادگی میتواند بررسی کند که
به همراه عمل ⊕ یک گروهاست.
به همین صورت گروهی دیگری را به همراه عمل ضرب به پیمانه m با کمی تغییر میتواند ساخت.
کاربرد گروهها
گروهها در زمینه علوم گوناگون مانند بلورشناسی، کوانتم و فیزیک و ... دارای کاربردهای فراوان هستند. به عنوان مثال در شیمی و بلورشناسی گروهها برای طبقه بندی ساختار بلورها و چندوجهیهای منظم، تقارنهای ملکولی استفاده میشوند.
بعلاوه از گروهها در زمینه رمزنگاری و مسایل امنیتی نیز استفاده فراوان میشود.
همچنین از مفاهیم موجود در این نظریه همانند قضایای سیلو، زیرگروههای نرمالف گروههای آبلی و ... در شاخههای گوناگون ریاضیات چون هندسه جبری، توپولوژی جبری، مسایل ترسیم پذیری، نظریه جبری اعداد و.. استفاده میشود.
نظریه گروه در شیمی
با توجه به تقارن موجود در ترکیبات شیمیایی، ترکیبات به گروههای مختلف تقارنی تقسیم میشوند. هر گروه خواص دارد که در طیف بینی کاربرد دارد.
مونوئیدها
آنالیز ریاضی:
آنالیز نام عمومی آن بخشهائی از ریاضیات است که با مفاهیم حد و همگرایی مربوطاند و در آنها موضوعاتی مثل پیوستگی و انتگرالگیری و مشتقپذیری و توابع غیرجبری بررسی میشود. این موضوعات را معمولاً در عرصه اعداد حقیقی یا اعداد مختلط و توابع مربوط به آنها بحث میکنند ولی میتوان آنها را در هر فضائی از موجودات ریاضی که در آن مفهوم "نزدیکی" (فضای توپولوژیک) یا "فاصله" (فضای متریک) وجود دارد بهکار برد. آنالیز ریاضی از کوششهای مربوط به دقیق کردن مبانی و تعریفهای حسابان سر برآورده است.
- انالیز ریاضی در واقع به نقاط استثنایی ریاضیات میپردازد . کلمه انالیز به همین معنی [: نقاط استثنایی] است .
مثلا در مورد انتگرال، انتگرال معمولی به انتگرال ریمان-اشتیل یس و انتگرال لبگ تعمیم مییابد. آنالیز ریاضی زمینهای ظریف و دقیق است.در واقع حسابان قسمت کاربردی و بدون در نظر گرفتن جزییات آنالیز محسوب میشود.
نالیز تابعی (Functional analysis) شاخهای از آنالیز ریاضی ست که به مطالعهٔ توابع ریاضی و عملکرد عملگرها (operators) بر روی آن توابع و نیز بررسی فضاهای ریاضی مربوط به آنها میپردازد. از جملهٔ موضوعات عمدهٔ مورد بحث در این زمینه، میتوان به تبدیلات گوناگون (همچون تبدیل فوریه)، معادلات دیفرانسیل، معادلات انتگرال، فضای باناخ، و فضای هیلبرت اشاره داشت.
توپولوژی شاخهای از ریاضیات است که به بررسی فضاهای توپولوژیک و خواص بنیادی فضا از جمله همبندی میپردازد. توپولوژی یکی از شاخههای نسبتاً جوان ریاضیات است.
نام گذاری
نام این رشته از واژههای یونانی توپو (τόπος) بهمعنی مکان و (Logos) بهمعنای شناخت گرفته شده است. بنابراین، توپولوژی یعنی مکانشناسی. فرهنگستان زبان و ادب فارسی برای توپولوژی واژهای معادل پیشنهاد نکرده و همان توپولوژی را در نظر گرفته است.
تاریخچه:
این مبحث نخستینبار توسط آنری پوانکاره (۱۹۱۲-۱۸۵۴) و در مقالهای با نام «
آنالیز مکان» بهصورت مجموعهای از روشها و مسایل، دستهبندی شد. این مبحث در ادامه پیشرفتهایی بنیادین داشت و در شکل دادن به ریاضیات قرن بیستم و امروز، نقشی اساسی بازی کرد.
در صحبت از توپولوژی معمولاً اشیایی مانند نوار موبیوس، بطری کلاین، گرهها و حلقهها نخستین چیزهایی هستند که به ذهن میآیند. اما برخی با عبارتی طنزآمیز توپولوژیستها را توصیف میکنند؛ آنها میگویند توپولوژیست کسی است که فرقی میان فنجان قهوه و پیراشکی نمیبیند!
تغییرشکل پیوسته (هموتوپی) یک فنجان قهوه به یک چنبره و برعکس.
در دهه ۱۶۷۰ میلادی، گتفرید ویلهلم لایبنیتس (۱۷۱۶-۱۶۴۶)، در نامهای به کریستین هویگنس (۱۶۲۹-۱۶۹۵)، به تشریح مفهومی پرداخت که بعدها به مهمترین هدف در مطالعه توپولوژی تبدیل شد:
من معتقدم ما به یک آنالیز دیگری هم نیاز داریم که کاملاً هندسی یا خطی باشد، بهگونهای که با مکان مستقیماً همان رفتاری را داشته باشد که جبر با مفهوم بزرگی دارد.
لایبنیتس رویای حساب دیفرانسیل و انتگرال اشکالی را در سر میپروراند که در آن فرد میتواند بهسادگی اعداد و اشکال را با هم ترکیب کند، مانند چندجملهایها، روی آنها عمل انجام دهد و به نتایج جدید و متقن هندسی دست پیدا کند. این دانش مکان، همان است که پوانکاره آن را «آنالیز مکان» نامید. ما نمیدانیم که لایبنیتس دقیقاً چه در سر داشت؛ اما این لئونارد اویلر (۱۷۰۱-۱۷۸۳) بود که نخستین مشارکتها را در این شاخهٔ جوان--که وی آن را
هندسه مکان مینامید--از خود ارائه داد. راهحل او برای مسئلهٔ پلهای کنیگسبرگ و فرمول مشهور اویلر، یعنی
(که در آن
تعداد رأس،
تعداد یال و
تعداد وجوه چندوجهی است)، نتایجی بودند که به موقعیتهای نسبی اشکال هندسی--و نه بزرگی آنها--بستگی داشتند.
در سده نوزدهم، کارل فردریک گاوس (۱۷۷۷-۱۸۵۵)، هنگامی که گرهها و حلقهها را بهعنوان تعمیمی از مدارهای سیارات مطالعه میکرد، به هندسه مکان علاقهمند شد. او با نامگذاری اشکال گرهها و حلقهها، یک دستگاه مقدماتی بهوجود آورد که با روش ترکیبیاتی، گرههای معینی را از یکدیگر مجزا میساخت. برنهارد ریمان (۱۸۲۶-۱۸۶۶) نیز از روشهای دانش نوپای آنالیز مکان، بهعنوان ابزاری بنیادین برای مطالعه توابع مختلط بهره جست.
یک نوار موبیوس تنها یک سطح دارد و یک لبه.
در طی سده نوزدهم، آنالیز بهعنوان دانشی ژرف و در عین حال ظریف پیشرفت پیدا میکرد. با آغاز از کارهای ژرژ کانتور (۱۸۴۵-۱۹۱۸)، ایدههایی از جمله پیوستگی توابع و همگرایی دنبالهها، بهگونهای فزاینده و در موقعیتهای کلی بررسی میشدند تا این که در سده بیستم، و در سال ۱۹۱۴، فلیکس هاوسدورف (۱۸۶۹-۱۹۴۲) ایده کلی فضای توپولوژیکی را مطرح کرد.
مفهوم بنیادین در توپولوژی، اندیشه پیوستگی است و این مفهوم برای نگاشتهای میان دو مجموعه که مجهز به مفهومی از «نزدیک بودن» باشند تعریف میشود (یعنی همان فضاهای توپولوژیکی) و البته این نزدیک بودن، تحت نگاشتهای پیوسته حفظ میشود. بدین ترتیب، میتوان گفت توپولوژی نوعی هندسه است که در آن خواص مهم یک شکل، آنهایی درنظر گرفته میشوند که تحت حرکتهای پیوسته (همئومورفیسمها) حفظ گردند. در این دیدگاه، توپولوژی بهصورت هندسه صفحاتی لاستیکگونه تعریف میشود.
مفاهیم:
توپولوژی یکی از زمینههای مهم ریاضیات است که از پیشرفت مفاهیمی از هندسی و نظریه مجموعهها مانند فضا، بعد، اشکال، تبدیلات و... بوجود آمده است. از جنبه تاریخی توپولوژی در سال ۱۸۴۷ به توسط لیستنگ، یکی از شاگردان گاوس، معرفی شد. نام دیگری که در آغاز بسط توپولوژی به این موضوع اطلاق میشد، آنالیز وضع (Analysis Situs) بود.
توپولوژی دارای زیرشاخههای زیادی است. بنیادیترین و قدیمیترین زیرشاخه، توپولوژی نقطه-مجموعه است که بنیادهای توپولوژی بر آن بنا شده است و به مطالعه در زمینههای فشردگی، پیوستگی و همبندی میپردازد. توپولوژی جبری نیز یکی دیگر از زیرشاخههای توپولوژی است که سعی در محاسبه درجه همبندی دارد. همچنین زیرشاخههایی مانند توپولوژی هندسی، توپولوژی گراف و توپولوژی ابعاد پایین نیز وجود دارند.
توپولوژی مطالعه ریاضیاتی روی خصوصیاتی است که در طی تغییر شکلها، ضربه خوردنها و کشیده شدن اشیاء، به طور ثابت حفظ میشوند (البته عمل پاره کردن مجاز نمیباشد). یک دایره به لحاظ توپولوژیکی همارز با یک بیضی میباشد که میتواند در داخل آن با کشیده شدن تغییر شکل یابد و یک کره با یک سطح بیضیوار همارز است (یعنی یک منحنی بسته تک بعدی و بدون هیچ محل تقاطع که میتواند در فضای دو بعدی جای گیرد)، مجموعه تمام وضعیتهای ممکن برای عقربههای ساعتشمار و دقیقهشمار با هم، به لحاظ توپولوژیکی با چنبره همارز است (یعنی یک سطح دوبعدی که میتواند در داخل فضای سه بعدی جای گیرد) و مجموعه تمام وضعیتهای ممکن برای عقربههای ساعتشمار، دقیقهشمار و ثانیهشمار با هم، به لحاظ توپولوژی با یک شیء سه بعدی همارز میباشد.
توپولوژی با منحنیها، سطوح و سایر اشیاء در صفحه و فضای سه بعدی مطرح گردید. یکی از ایدههای اصلی در توپولوژی این است که اشیاء فضایی مثل دایرهها و کرهها در نوع خود میتوانند به عنوان اشیاء محسوب شوند و علم اشیاء ارتباطی با چگونگی نمایش یافتن یا جای گرفتن آنها در فضا ندارد.
توپولوژی با مطالعه مواردی چون اشیاء فضایی از قبیل منحنیها، سطوح، فضایی که ما آن را جهان مینامیم، پیوستار فضا زمان با نسبیت عمومی، فراکتالها، گرهها، چند شکلیها (اشیایی هستند که برخی خصوصیات فضایی اصلی آنها مشابه با جهان ما میباشد)، فضاهای مرحلهای که در فیزیک با آنها مواجه میشویم (مثل فضای وضعیتهای قرار گرفتن عقربهها در ساعت)، گروههای متقارن همچون مجموعه شیوههای چرخاندن یک رأس و غیره در ارتباط است.
توپولوژی برای جدا سازی اتصال ذاتی اشیاء و در عین حال کنار گذاشتن ساختار جزء به جزء آنها قابل استفاده میباشد. اشیاء توپولوژیکی اغلب به صورت رسمی به عنوان فضاهای توپولوژیکی تعریف میشوند. اگر دو شیء دارای خصوصیات توپولوژیکی مشابه باشند، گفته میشود که آنها هم ریخت هستند. البته اگر دقیق تر بگوییم، خصوصیاتی که با کشیدن یا کج کردن یک شیء تخریب نمیشوند، در واقع خصوصیاتی هستند که به واسطه همسانگری حفظ میشوند نه به واسطهٔ هم ریختی؛ همسانگری با کج کردن اشیاء دیگر در ارتباط است در حالیکه همریختی، خصیصه ذاتی است.
حدود سال ۱۹۰۰، پوانکاره معیاری از توپولوژی را تحت عنوان هوموتوپی (Homotopy) طراحی کرد. به طور خاص دو شیء ریاضیاتی زمانی هوموتوپیک خوانده میشوند که یکی از آنها بتواند به طور پیوسته به شکلی مشابه شکل دیگری تغییر یابد.
توپولوژِی با مطالعاتی که در زمینهٔ سوالاتی که در هندسه مطرح بود، آغاز شد. مسئله ۷ پل کانیگزبرگ اویلر جز اولین نتایج توپولوژیک بود. نمونه رابطه توپولوژیکی، فرمول اویلر است در مورد چندوجهیها که تعداد رئوس (v) منهای تعداد خطوط یا لبهها (e) باضافه تعداد سطوح (f) همیشه برابر است با ۲ است.(v - e + f =۲)
فرمول اویلر در سال ۱۷۵۲ منتشر شد ولی ۶۳ سال بعد در سال ۱۸۱۳ ریاضیدان سویسی بنام لیولیر اثبات کرد که فرمول اویلر برای چندوجهیهای سوراخدار صحیح نیست و فرمول کامل چنین است: v – e + f = ۲g، که g تعداد سوراخها است.
۵۲ سال بعد از لیولیر، در سال ۱۸۶۵، موبیوس نوار خود را معرفی کرد که فقط یک رویه دارد و از نواری بدست میآید که قبل از چسباندن دو سرش به یکدیگر، یک سر را ۱۸۰درجه بچرخانیم و بعد بچسبانیم. ۱۷ سال بعد در سال ۱۸۸۲ ریاضیدان آلمانی فلیکس کلاین بطری معروف به «بطری کلاین» را معرفی کرد که درون و برون آن از هم متمایز نیستند و بعبارتی دیگر حجم آن صفر است. توپولوژی مدرن وابسته به ایدهٔ تئوری مجموعههای کانتر میباشد که در اواخر قرن ۱۹ مطرح شد.
مجموعه X به همراه گردایه T از زیرمجموعههای X را یک فضای توپولوژیکی گویند هر گاه: مجموعههای تهی و X، عضو T باشند. اجتماع هر گردایه از مجموعههای عضو T در T قرار دارد. اشتراک هر دو مجموعه عضو T در T قرار دارد. مجموعه T را یک توپولوژی روی X میگوییم. همچنین اعضای T مجموعههای باز در X و متتم آنها مجموعههای بسته در X هستند. اعضای X را نقاط مینامیم. وی یک مجموعه مانند X توپولوژیهای متعددی میتوان تعریف کرد (حداقل دو توپولوژی گسسته و ناگسسته را میتوانیم روی X تعریف کنیم). حال فرض کنید T۱ و T۲ دو توپولوژی روی X هستند. اگر هر عضو T۱، عضوی از T۲ نیز باشد آنگاه میگوییم T۲ ظریفتر از T۱ است. در این صورت اثباتی که برای وجود یک مجموعه باز معین ارائه میدهیم در مورد توپولوژی ظریفتر هم برقرار است. توابع پیوسته: فرض میکنیم (X,T) و (Y,U) دو فضای توپولوژیک دلخواه باشند: تابع در نقطه x واقع در X را پیوسته گوییم، هرگاه به ازای هر مجموعه باز شامل f(x) مانند BY، مجموعه بازی مانند BX شامل x وجود داشته باشد به طوری که f[BX] زیر مجموعه BY باشد. مثال: R یک فضای توپولوژیکی است و مجموعههای باز در آن بازههای باز هستند. به طور کلی فضای اقلیدسی Rn یک فضای توپولوژیکی است و مجموعههای باز در آن گویهای باز هستند. چند قضیه توپولوژی: هر بازه بسته با طول متناهی در Rn فشردهاست. و معکوس تصویر پیوسته یک فضای فشرده، فشردهاست. قضیه تیخونوف: حاصلضرب فضاهای فشرده، یک فضای فشردهاست. زیر مجموعه فشرده یک فضای هاسدورف، بستهاست. هر فضای متری هاسدورف است. به همین ترتیب میگوییم تابع در مجموعهٔ A واقع در X پیوستهاست رد صورتی که در تمام نقاط A پیوسته باشد. قضیه: تابع در X پیوستهاست اگر و تنها اگر به ازای هر زیر مجموعه باز در Y مانند BY، مجموعهیf[BY] − ۱ زیر مجموعه باز X باشد. به طور خلاصه: فرض کنید X و Y دو فضای توپولوژیکی هستند. یک تابع بین X و Y را پیوسته میگوییم اگر تصویر معکوس هر مجموعه باز در X یک مجموعه باز در Y باشد. در واقع نشان میدهیم که هیچ شکستگی یا انفصال در تابع وجود ندارد.
تعریف ریاضی یک
فضای توپولوژیکی، زوج مرتبی مانند
است که در آن
یک مجموعه، و
نیز گردایهای از زیرمجموعههای
است، بهگونهای که اصول موضوع زیر ارضا شوند:
۱. اجتماع هر گردایه از مجموعههای عضو
در
قرار داشته باشد؛۲. اشتراک هر تعداد متناهی مجموعه عضو
در
قرار داشته باشد؛ یعنی اشتراک هر گردایه متناهی از مجموعههای عضو
در
قرار داشته باشد؛۳. مجموعههای تهی و
، عضو
باشند. گردایهٔ
، توپولوژی تعریف شده روی
نام دارد. اگر توپولوژی تعریف شده روی
مشخص باشد، فضای توپولوژیکی
، بهطور سادهشدهٔ
نوشته و به آن فضای
گفته میشود. همچنین، اعضای
،
مجموعههای باز در و متمم آنها،
مجموعههای بسته در نام دارند. اگر
یک فضای توپولوژیکی باشد، به اعضای آن
نقطه گفته میشود. اگر
نقطهای از یک مجموعهٔ باز مانند
باشد، به
، «یک همسایگی از
» نیز گفته میشود.
مثال
روی
توپولوژیهای گوناگونی میتوان تعریف کرد؛ اگر مجموعههای باز را همان بازههای باز درنظر بگیریم، در اینصورت به توپولوژی بهدست آمده،
توپولوژی استاندارد روی
گفته میشود. با تعمیم این ایده، مجموعههای باز در توپولوژی
معمولی روی فضای اقلیدسی
، گویهای باز هستند.
مقایسهٔ توپولوژیهای تعریف شده روی یک مجموعه روی یک مجموعه مانند
توپولوژیهای متعددی میتوان تعریف کرد--دستکم دو توپولوژی گسسته و ناگسسته. در توپولوژی گسسته، هر زیرمجموعه از
، یک مجموعه باز درنظر گرفته میشود و در توپولوژی ناگسسته یا بیمایه، تنها مجموعههای باز، مجموعهٔ
و تهی هستند.
برای هر توپولوژی
تعریف شده روی
داریم
. پس درشتترین توپولوژی که روی یک مجموعه میتوان تعریف کرد، توپولوژی ناگسسته یا بیمایه، و ظریفترین توپولوژی قابل تعریف روی یک مجموعه، توپولوژی گسستهاست.
حال فرض کنید
و
دو توپولوژی روی
باشند. اگر هر عضو
، عضوی از
نیز باشد، آنگاه گفته میشود
ظریفتر از
است. در این صورت اثباتی که برای وجود یک مجموعهٔ باز معین ارائه داده میشود، در مورد توپولوژی ظریفتر هم برقرار است.
چند قضیه از توپولوژی
- هر بازه بسته با طول متناهی در Rn فشرده است. و معکوس
- تصویر پیوسته یک فضای فشرده، فشردهاست.
- قضیه تیخونوف: حاصلضرب فضاهای فشرده، یک فضای فشردهاست.
- زیر مجموعه فشرده یک فضای هاسدورف، بسته است.
- هر فضای متری هاسدورف است.
جبر خطّی شاخهای از ریاضیات است که به بررسی و مطالعۀ ماتریسها، بردارها، فضاهای برداری (فضاهای خطّی)، تبدیلات خطی، و دستگاههای معادلات خطی میپردازد.
کاربردها
جبر خطّی و کارائیهای فراوان و گوناگون آن در ریاضیات و محاسبات گسسته طیف گسترده و وسیعی را شامل میگردد. علاوه بر کاربردهای آن در زمینههایی از خود ریاضیات همانند جبر مجرد، آنالیز تابعی، هندسۀ تحلیلی، و آنالیز عددی، جبر خطّی استفادههای وسیعی نیز در فیزیک، مهندسی، علوم طبیعی، و علوم اجتماعی پیداکرده است.
مقدمه
آغاز نمودن مبحثی با اهمیت و همهجاگیری جبر خطی یکی از دشوارترین کارهاست، چرا که، با جهتگیریها، تعبیرات، تعمیمات، و آیندهبینیهای زیادی روبرو میشویم. شاید یکی از انتخابهای مناسب این گونه باشد:
ماتریس و بردار زیر را در نظر میگیریم:
با ضرب ماتریس و بردار داریم:
نتیجهٔ فوق را میتوان در ترازهای معنائی گوناگونی مورد دقت و بررسی قرار داد. برخی از ملاحظات این گونه است:
ماتریس
به عنوان عملگری بر روی بردار
عمل نموده و آنرا به بردار
تبدیل کرده است.
میتواند ثابت انگاشته شده و دستگاهی ساده را نمایندگی کند، که در آن صورت، بردار
اطلاعات یا دادههایی را مینمایاند که به نوعی به سیستم داده شده است.
سیستم
درست مثل پردازشگری اطلاعات را به دانش تبدیل میکند. شاید یکی از روشنترین مثالهای کوتاه برای مفهوم فرایند تبدیل اطلاعات به دانش همین باشد.
ویژهمقدار
مقالهٔ اصلی: ویژهمقدار
ویژهمقدار و ویژهبردار از جملهٔ پرکاربردترین و جوهریترین مؤلفههای ماتریسها و عملگرهای خطی میباشد. مفهوم و عملکرد این اشیاء ریاضی را باید از جنس تلخیص، فشردهسازی اطلاعات، و ساده و آسان حل کردن مسائل خطی دشوار دانست.
فضاهای برداری
مقالهٔ اصلی: فضاهای برداری
از آنجا که بسیاری از کمیتهای فیزیکی مثل نیرو، سرعت و شتاب هم اندازه (بزرگی) دارند و هم راستا، آنها را کمیتی برداری درنظر میگیرند.
کتاب و جزوه
از سال گذشته درس جبر خطی به عنوان پیشنیاز درس تحقیق در عملیات و آمار و احتمالات مهندسی معرفی شد و دانشجویان ورودی ۸۹ و ما بعد باید این درس رو بگذرونن. برای دانلود کتاب و جزوات درس جبر خطی مهندسی صنایع که به تازگی به دروس مهندسی صنایع اضافه شده کلیک کنید.
جبر خطی عددی
نظریه گراف[۱] شاخهای از ریاضیات است که دربارهٔ گرافها بحث میکند. این مبحث در واقع شاخهای از توپولوژی است که با جبر و نظریه ماتریسها پیوند مستحکم و تنگاتنگی دارد. نظریهٔ گراف برخلاف شاخههای دیگر ریاضیات نقطهٔ آغاز مشخصی دارد و آن انتشار مقالهای از لئونارد اویلر، ریاضیدان سوئیسی، برای حل مسئله پلهای کونیگسبرگ در سال ۱۷۳۶ است.
[۲]
پیشرفتهای اخیر در ریاضیات، به ویژه در کاربردهای آن موجب گسترش چشمگیر نظریهٔ گراف شده است به گونهای که هماکنون نظریهٔ گراف ابزار بسیار مناسبی برای تحقیق در زمینههای گوناگون مانند نظریه کدگذاری، تحقیق در عملیات، آمار، شبکههای الکتریکی، علوم رایانه، شیمی، زیستشناسی، علوم اجتماعی و سایر زمینهها گردیده است.
[۳]
نمایش تصویری یک گراف
تاریخچه
برخلاف شاخههای دیگر ریاضیات، سیر نظریهٔ گراف آغاز معینی در زمان و مکان دارد و آن مسئلهٔ هفت پل کونیگسبرگ است که در سال ۱۷۳۶ توسط لئونارد اویلر حل شد. در سال ۱۷۵۲ قضیهٔ اویلر برای گرافهای مسطح ارائه میشود. اما پس از آن به مدت تقریباً یک قرن فعالیت اندکی در این زمینه صورت گرفت.
در سال ۱۸۴۷، گوستاو کیرشهف نوع خاصی از گرافها به نام درخت را مورد بررسی قرار داد. کیرشهف این مفهوم را هنگام تعمیم قوانین اهم برای جریان الکتریکی در کاربردهایی که حاوی شبکههای الکتریکی بودند بهکار گرفت. ده سال بعد، آرتور کیلی همین نوع گراف را برای شمارش ایزومرهای متمایز هیدروکربنهای اشباع شدهٔ C
nH
۲n+۲ بهکار برد.
[۴]
در همین دوران شاهد حضور دو ایدهٔ مهم دیگر در صحنه هستیم. ایدهٔ اول حدس چهار رنگ بود که نخستین بار توسط فرانسیس گوثری در حدود سال ۱۸۵۰ مورد تحقیق قرار گرفت. این مسئله سرانجام در سال ۱۹۷۶، توسط کنث ایپل و ولفگانگ هیکن و با استفاده از یک تحلیل رایانهای پیچیده حل شد.
[۵]
ایدهٔ مهم دوم، دور همیلتونی بود. این دور به افتخار سر ویلیام روآن همیلتون نامگذاری شده است. او این ایده را در سال ۱۸۵۹ برای حل معمای جالبی حاوی یالهای یک دوازده وجهی منتظم بهکار گرفت. یافتن جوابی برای این معما چندان دشوار نیست ، ولی ریاضیدانان هنوز در پی یافتن شرایطی لازم و کافی هستند که گرافهای بیسوی حاوی مسیر یا دورهای همیلتونی را مشخص کنند.
پس از این کارها تا بعد از سال ۱۹۲۰ فعالیت اندکی در این زمینه صورت گرفت. مسئلهٔ مشخص کردن گرافهای مسطح را کازیمیر کوراتوفسکی، ریاضیدان لهستانی، در سال ۱۹۳۰ حل کرد. نخستین کتاب دربارهٔ نظریهٔ گراف در سال ۱۹۳۶ منتشر شد. این کتاب را ریاضیدان مجار، دنش کونیگ، که خود محقق برجستهای در این زمینه بود، نوشت. از آن پس فعالیتهای بسیاری در این زمینه صورت گرفته و رایانه نیز در چهار دههٔ اخیر به یاری این فعالیتها آمده است.
[۶]
تعریف
تعریف دقیقتر گراف به این صورت است، که گراف مجموعهای از رأسها است، که توسط خانوادهای از زوجهای مرتب که همان یالها هستند به هم مربوط (وصل) شدهاند.
یالها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جادهای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید. همچنین برای اینکه فاصله بین دو شهر را در گراف نشان دهید، میتوانید از گراف وزن دار استفاده کنید و مسافت بین شهرها را با یک عدد بر روی هر یال نشان دهید.
آغاز نظریهٔ گراف به سدهٔ هجدهم بر میگردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پلهای کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بودهاست.
مهمترین کاربرد گراف مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایجسترا یا الگوریتم کروسکال و... را بر روی آن اعمال نمود.
یکی از قسمتهای پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گرافهایی میپردازد که میتوان آنها را به نحوی روی صفحه کشید که یالها جز در محل راسها یکدیگر را قطع نکنند. این نوع گراف در ساخت جادهها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار میرود.
نظریه گراف یکی از پرکاربردترین نظریهها در شاخههای مختلف علوم مهندسی (مانند عمران)، باستانشناسی (کشف محدوده یک تمدن) و... است.
روابط میان راسهای یک گراف را میتوان با کمک ماتریس بیان کرد.
برای نمایش تصویری گرافها معمولاً از نقطه یا دایره برای کشیدن راسها و از کمان یا خط راست برای کشیدن یال بین راسها استفاده میشود.
اندازه گراف
اندازه گراف تعداد یالهای یک گراف است و به صورت
بیان میشود.
درجه راسها
در نظریه گرافها، درجه یک راس به تعداد یالهای متصل به آن راس گفته میشود. به عبارت دیگر، درجه یک راس تعداد همسایگی (مجاورت)های مستقیم یک راس را بیان میکند. از آنجا که هر یال در گراف دو راس را به هم وصل میکند، مجموع درجه راسهای یک گراف با دو برابر تعداد یالهای ان گراف برابر است.
انواع گراف
گراف همبند گرافی است که بین همه ی راسهای آن مسیری وجود داشته باشد.
گراف هی وود(Heawood Graph)
گراف کنزر(Kneser)
گراف کامل
در نظریه گراف، یک گراف کامل، گرافیاست که بین هر دو راس آن دقیقاً یک یال وجود داشته باشد. یک گراف کامل از مرتبه n، دارای n راس و
یال است که آن را با
نشان میدهند. یک گراف کامل یک گراف منتظم از درجه n-۱ است.
گراف های کاملی که p≥3 قطعاً همیلتونی هستند.
گراف های کاملی که p≥3 و p فرد باشد ( p=2k+1) اویلری هستند، چون درجه ی هر راس زوج است.
گراف پترسن
گراف پترسن گرافی با ۱۰ راس و ۳- منتظم است
گراف دو بخشی
مفهوم شهودی
فرض کنید در یک شرکت صنعتی تعدادی شغل بدون متصدی میباشند و تعدادی متقاضی برای این مشاغل اعلام آمادگی نمودهاند. حال این سوال مطرح میشود که آیا میتوان به هر متقاضی شغلی متناسب او اختصاص داد؟ برای حل چنین مسئلهای که به مسئلهٔ تخصیص موسوم است، با استفاده از گراف میتوان وضعیتهای خاص را پیاده سازی نمود. بدین ترتیب که گروهی که متقاضی مشاغل هستند در مجموعهای به نام X و مجموعه مشاغل بدون متصدی را در مجموعهای به نام Y قرار میدهیم. گراف رسم شده چنین است که به بعضی از اعضای مجموعه X یک یا چند عضو از مجموعه Y توسط یالها وصل مینماید. به عبارت دیگر گراف بوجود امدی دارای یالهای xy است که مر متقاضی x را از مجموعه X به شغلهای مناسب y از مجموعه Y متصل مینماید. به عبارت دقیقتر هیچ دو راس متعلق به مجموعه X (متفاضیان) یا هیچ دو راس متعلق به مجموعه Y (مشاغل) توسط هیچ یالی به هم متصل نمیباشند. چنین گرافی را گراف دوبخشی یا دوپارچه میگویند.
تعریف
گراف دوبخشی گرافی است که بتوان مجموعه رئوس آن را به دو مجموعه X و Y چنان افراز نمود که هر یال آن دارای یک انتها در X و یک انتها در Y باشد، به گونهای که هیچ دوراسی در X یا در Y با هم مجاور نباشند. چنین افرازی را دوبخشی کردن گراف مینامند.
- یادآوری: منظور از افراز یک مجموعه چون A به چند مجموعه، تقسیم مجموعه A به چند مجموعه ناتهی دیگر است که باهم اشتراکی نداشته باشند و اجتماع همه آنها برابر مجموعه A باشد. و در اینجا اگر V به عنوان مجموعه رئوس باشد افراز V به دو مجموعه X و Y (ناتهی) به این صورت است که: XY = V و XY =
- مثال
به عنوان مثال گراف زیر یک گراف دو بخشی است:
مثالی از يک گراف دو بخشی
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از تمام زیرمجموعههای دو عضوی V میباشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد و هیچ طوقهای (یعنی یالی که رأس را به خودش وصل میکند) نیز وجود نداشته باشد.
[۷]
گراف همیلتونی
گراف چرخ
هر گراف G که دارای n راس باشد کهn≥۴ و یکی از رئوس از درجهٔ n-۱ و بقیه از درجهٔ سه باشند، را یک گراف چرخ مینامیم- مانند مثالهای زیر:
گراف چرخn راسی را با
nW نمایش میدهیم.
گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه میگوییم.
گراف مکعبی
یک گراف «k مکعب» (k-Cube) گرافی است که رئوس آنk تایی از «صفر» و «یک» هستند که دو رأس آن به یکدیگر متصل هستند اگر و فقط اگر دو رأسشان دقیقاً در یک مؤلفه با یکدیگر تفاوت داشته باشند. بهعبارت دیگر اگر kعددی طبیعی باشد منظور از «kمکعب» گرافی است که رأسهای آن همهٔ دنبالههای رقمی از «صفر» و «یک» هستند و دو رأس در این گراف مجاور بوده هرگاه دنبالههای متناظرشان دقیقاً در یک مؤلفه اختلاف داشته باشند (شکل ۱).
میتوان نشان داد که یک گراف «k مکعب» (k-Cube) دارای ویژگیهایی نظیر ذیل است:
- تعداد رؤوس =۲k
- تعداد یالها=k*۲(k-۱)
- گرافی «دوبخشی» (Bipartite) است.
گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعهای متناهی و ناتهی است و E زیرمجموعهای از مجموعهٔ تمام زوج مرتبهای متشکل از اعضای V است.
گراف جهت دارو کاربردهای آن: گراف جهت دار D، یک سه تایی مرتب(O(D) و A(D) و (V(D)است که تشکیل شده از یک مجموعه ناتهی V(D) از راسها ویک مجموعه (D) A مجزای از V(D)از کمانها و یک تابع وقوع O(D)که به هر کمان D یک زوج مرتب از راسهای D- که الزاماً متمایز نیستند- را نسبت میدهد. اگر a یک کمان وu,v دو راس باشند به طوری که(u,v) =(a)O (D)، آنگاه میگوئیم که u,a را به v وصل کرده است؛ u، دم v,a سرa نامیده میشود.
گراف مسطح: گراف مسطح گرافی است که میتوان آن را در یک صفحه محاط کرد به گونهای که یالهایش یکدیگر را تنها در راسها قطع کنند. به این گراف هامنی نیز گفته میشود.
در بین گراف های کامل فقط گراف هایی با تعداد راس مساوی یا کمتر از 5 (p≤5) را، می توان به صورت مسطح رسم کرد.
گراف وزن دار: در یک گراف وزن دار، به هر یال یک وزن (عدد) نسبت داده میشود. معمولاً اعداد حقیقی به عنوان وزن یالها استفاده میشوند. اما بسیاری از الگوریتمهای پر کاربرد فقط برای گرافهایی که دارای وزن صحیح یا مثبت هستند طراحی شدهاند.
خصوصیات گرافهای خاص
- اگر درجهٔ همهٔ راسها در گراف ساده با هم برابر و برابر بزرگترین درجهٔ ممکن (یعنی p-۱) باشد، گراف مورد نظر منتظم کامل است. در این گونه گرافها، رابطهٔ میان رأسها و یالها چنین است:
که در آن
تعداد راسها، و
تعداد یالها است.
- اگر گراف همبند باشد (یعنی از هر نقطه بتوان به یک نقطه دلخواه دیگر رسید) ولی دور نداشته باشد (یعنی هیچ نقطهای از دوراه به نقطهٔ بعدی نرسد) میگویند گراف درختی است. در اینگونه گرافها فرمول زیر صدق میکند (شرط لازم):
که در آن
تعداد رأسها، و
تعداد یالها است.
[۸]
- گراف اویلری و همیلتونی:گاهی اوقات ما میخواهیم در یک گراف حرکت کنیم. به اینصورت که از راسی به راسی دیگر برویم. در اینصورت ممکن است برای ما مهم باشد که از روی یال یا راس تکراری حرکت نکنیم(مشابه مسالهٔ فروشندهٔ دوره گرد). این مساله در صرفه جویی زمان و هزینه هم مهم است.(یعنی مبحث بهینه سازی). دراینجا دو موضوع گرافهای اویلری(دور زدن در گراف بدون یال تکراری)و همیلتونی(دور زدن بدون راس تکراری) مطرح میشود. براحتی میتوان بررسی کرد که راسهای گراف اویلری باید درجهٔ زوج داشته باشند. اما اینکه شرایط کامل لازم و کافی برای همیلتونی بودن یک گراف چیست هنوز حل نشده ماندهاست.
گراف های کاربردی:
گراف بازهها
اگر بخواهیم گراف بازهای را در یک جمله تعریف کنیم میتوانیم بگوییم گرافی است که رئوس آن متناظر با بازههای باز اعداد حقیقی است و رئوسی به هم وصل میشوند که بازههای متناظر با آنها اشتراک داشته باشند.
برای مثال گراف مربوط به بازههای : (۶٬۹) , (۳٬۸) , (۳٬۴) , (۲ , ۵) , (۱٬۴) , (۰٬۲) این گونه خواهد بود :
حال سوالاتی مطرح میشود به مانند ۱.این گرافها چه خواص کاربردی دارند ؟ ۲.یا چه گرافهایی میتوانند بازهای باشند؟
در اینجا شرطی لازم برای بازهای بودن گراف ارایه میکنیم که یک گراف اگر دارای حفره باشد حتماً بازهای نمیباشد. حفره :دوری با اندزهٔ بزرگ تر از ۳ گویند که هیچ یالی بین رئوس غیر متوالی در آن دور نباشد.
برای مثال گراف abcde بازهای نمیباشد به خاطر وجود دور abde
کاربردها
از گرافها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده میشود. ساختارهای زیادی را میتوان به کمک گرافها به نمایش در آورد. برای مثال برای نمایش چگونگی رابطه وب سایتها به یکدیگر میتوان از گراف جهت دار استفاده کرد. به این صورت که هر وب سایت را به یک راس در گراف تبدیل میکنیم و در صورتیکه در این وب سایت لینکی به وب سایت دیگری بود، یک یال جهت دار از این راس به راسی که وب سایت دیگر را نمایش میدهد وصل میکنیم.
از گرافها همچنین در شبکهها، طراحی مدارهای الکتریکی، اصلاح هندسی خیابانها برای حل مشکل ترافیک، و.... استفاده میشود. مهمترین کاربرد گراف مدلسازی پدیدههای گوناگون و بررسی بر روی آنهاست. با گراف میتوان به راحتی یک نقشه بسیار بزرگ یا شبکهای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و... را بر روی آن اعمال نمود. در این جا به بررسی گرافهایی میپردازد که میتوان آنها را به نحوی روی صفحه کشید که یالها جز در محل راسها یکدیگر را قطع نکنند. این نوع گراف در ساخت جادهها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار میرود.
کاربرد گراف بازهها از گرافها برای حل مسایل زیادی در ریاضیات و علوم کامپیوتر استفاده میشود. ساختارهای زیادی را میتوان به کمک گرافها به نمایش در آورد.
درخت و ماتریس درخت در رشتههای مختلفی مانند شیمی مهندسی برق و علم محاسبه کاربرد دارد. کیرشهف در سال ۱۸۴۷ میلادی هنگام حل دستگاههای معادلات خطی مربوط به شبکههای الکتریکی درختها را کشف و نظریه درختها را بارور کرد. کیلی در سال ۱۸۵۷ میلادی درختها را در ارتباط با شمارش ایزومرهای مختلف هیدروکربنها کشف کرد وقتی مثلا میگوییم در ایزومر مختلف c4h۱۰ وجود دارد منظورمان این است که دو درخت متفاوت با ۱۴ راس وجود دارند که درجه ۴ راس از این ۱۴ راس جهار و درجه هر یک از ۱۰ راس باقیمانده یک است. اگر هزینه کشیدن مثلا راه آهن بین هر دو شهر ازp شهر مفروض مشخص باشد ارزانترین شبکهای که این p شهر را به هم وصل میکند با مفهوم یک درخت از مرتبه p ارتباط نزدیک دارد. به جای مساله مربوط به راه آهن میتوان وضعیت مربوط به شبکههای برق رسانی و لوله کشی نفت و لوکشی گاز و ایجاد کانالهای آبرسانی را در نظر گرفت. برای تعیین یک شبکه با نازلترین هزینه از قاعدهای به نام الگوریتم صرفه جویی استفاده میشود که کاربردهای فراوان دارد. از گرافها میتوان به عنوان کدهای کمکی نام برد که به --- Playerها در بالا بردن قابلیتهای آنها کمک میکنند. گرافها دارایی مزایای مختلفی هستند که شفاف تر کردن و واضحتر کردن تصویر و کاهش مصرف CPU به عنوان یکی از اصلیترین مزایای آنها بشمار میرود.
مدول (جبر)
مدولها از ابزارهای کارامد برای مطالعه ساختارهای جبری اصلی مانند گروهها و حلقه هاهستند. مدولها تعمیم طبیعی فضاهای برداری هستند فقط بجای میدان روی یک حلقه تعریف میشوند. در حالت کلی مفهوم پایه برای مدولها تعریف نمیشود و مدولهای دارای پایه موجودات خاصی هستند که به مدولهای آزاد موسومند.