بیردۆزی چوار-ڕه‌نگه‌كه‌

نه‌شخه‌ی ئه‌مه‌ریكا ته‌نها ٤ ره‌نگ به‌كارهاتووه‌.
نه‌شخه‌ی ئه‌مه‌ریكا ته‌نها ٤ ره‌نگ به‌كارهاتووه‌.

بۆ یه‌كه‌م جار بیردۆزی چوار-ڕه‌نگه‌كه‌ ده‌گه‌رێته‌وه‌ بۆ سالی 1852 كاتێك Francis Guthrie بریتانی خه‌ریكی ره‌نگكردنی نه‌خشه‌ی شارو شارۆچكه‌كانی ئینگلته‌را بوو تێبینی ئه‌وه‌ی كرد كه‌ ته‌نها پێویستی به‌ چوار ڕه‌نگ هه‌یه‌ بۆ ڕه‌نگكردنی سه‌رجه‌م نه‌خشه‌كه‌ . دواتر له‌ پرسیاری له‌ براكه‌ی كرد كه‌ ناوی Frederick بوو  كه‌ ئایا ده‌توانرێت به‌ بۆ چونی ئه‌و  بۆ هه‌موو نه‌خشه‌یه‌ك ته‌نها چوار ڕه‌نگ به‌كاربهێنرێت بۆ ڕه‌نگكردنی؟ هه‌لبه‌ت مه‌رجه‌كه‌ ئه‌وه‌یه‌ كه‌ نابێت هیچ دوو شارۆچكه‌یه‌كی ته‌نیشت یه‌ك هه‌مان ڕه‌نگیان هه‌بێت. واته‌ هه‌ردوو شارۆچكه‌یه‌ك كه‌ سنوری نێوانیان هێلێك بوو ( نه‌ك ته‌نها خالێك) ئه‌وا ئه‌و دوو شارۆچكه‌یه‌ به‌ دراوسێی یه‌كتر داده‌نرێن و پێویسته‌ ڕه‌نگه‌كانیان جیاوازبیت.

دواتر هه‌ردوو براكه‌ فریدیریك و گۆسیری په‌یوه‌ندیان كرد به‌ دیمۆرگان DeMorgan { به‌لی یاسای دیمۆرگان له‌مه‌وه‌ هاتووه‌}  . وه‌ له‌ سالی 1878 بۆیه‌كه‌مجار ئه‌م كۆنجێكته‌ره‌ به‌شێوه‌ی چاپ بلاوكرایه‌وه‌ كه‌ دیاره‌  ئازایه‌تیه‌كه‌یش گه‌راته‌وه‌ بۆ كه‌یلی Cayley { زیاتر به‌ كاره‌كانی له‌ بواری جه‌بری ئه‌بستراكت ناسراوه‌}.

سالێك دوای بلاوكردنه‌وه‌ی كۆنجێكته‌ره‌كه‌ { مه‌به‌ست له‌ كۆنجێكته‌ر ده‌سته‌واژه‌یه‌كی بیركاریه‌ كه‌ نازانرێت راسته‌ یاخود هه‌ڵه‌} یه‌كه‌م سه‌لماندن بۆ ئه‌م كۆنجێكته‌ره‌ خرایه‌ روو، كه‌ له‌لایه‌ن Kempe بوو، دوای 11 ساڵ له‌بلاوكردنه‌وه‌ی یه‌كه‌م سه‌لماندن له‌لایه‌ن Heawood توانرا پیشانبدرێ كه‌ سه‌لماندنه‌كه‌ی Kempe هه‌ڵه‌یه‌. پاشان له‌ سالی 1880 سه‌لماندنێكی دیكه‌ له‌لایه‌ن Tait خرایه‌ روو، زۆری نه‌برد دوای سالێك له‌لایه‌ن Petersen له‌ 1891 توانی كه‌مووكورتیه‌ك له‌ سه‌لماندنه‌كه‌ Tait بدۆزێته‌وه‌. هه‌ردوو سه‌لماندنه‌ هه‌ڵه‌بوون به‌لام له‌رووی زانستیه‌وه‌ سودی خۆیان هه‌بوو { له‌بیركاری گه‌ر سه‌لماندێك راست نه‌بوو مانای ئه‌وه‌ نیه‌ ئیتر فرێده‌درێت به‌لكو زۆرجار هه‌وڵده‌درێت هه‌له‌كه‌ راستبكرێته‌وه‌ یان هه‌ر هیچنه‌بێت كۆمه‌لێك سودی لاوه‌كی لێوه‌ربگیریت}. Kempe توانی شتێك بدۆزێته‌وه‌ كه‌ دواتر نای لێنرا  زنجیره‌ی كه‌مپی (Kempe chains) هه‌روه‌ها Tait توانی هاوتایه‌ك بۆ بیردۆزی چوار-ڕه‌نگ بدۆزێته‌وه‌ له‌ڕێگه‌ی  3-نوك-ڕه‌نگكردنه‌وه‌ { كه‌ زیاتر تایبه‌ته‌ به‌ تیۆری گراف }.

له‌دوای ئه‌وانه‌ی سه‌ره‌وه‌ باسكران، گرنگترین به‌شداریكرنێك بۆ سه‌لماندنی ئه‌م بیردۆزه‌ له‌لایه‌ن بیركاریزانی ئه‌مه‌ریكی Birkhoff وه‌ بوو كاتێك كاره‌كانی ئه‌م ڕێگایان خۆشكرد بۆ Franklin تا له‌ساڵی 1922 بتوانیت بیردۆزه‌كه‌ بسه‌لمێنێت بۆ نه‌خشه‌یه‌ك كه‌ له‌ 25 هه‌رێم یان كه‌متر پێكهاتووه‌، نابێت كه‌ باسی بیردۆزی چوار-ڕه‌نگه‌كه‌ ده‌كه‌ین ناوی Heesch له‌یادبكه‌ین كه‌ ئه‌و بووه‌ هۆی گه‌شه‌پێدانی دوو چه‌مك سه‌باره‌ت به‌م بیردۆزه‌ چه‌مكه‌كانیش بریتیبوون له‌ هه‌ڵپه‌ساردن و دابه‌زاندن  ( reducibility and discharging) كه‌ ئه‌م دوو چه‌مكه‌ رێگه‌ خۆشكه‌ربوون بۆ سه‌لماندنی كۆتایی بیردۆزه‌كه‌ .

له‌سالی 1976 دا سه‌لماندنی بیردۆزی چوار-ڕه‌نگه‌كه‌ له‌لایه‌ن Appel and Haken خرایه‌ رووه كه‌ دیاره‌ گرنگی كاره‌كانی Heesch به‌سه‌ر سه‌لماندنه‌كه‌وه‌ به‌ته‌واوه‌تی دیاربووه‌.

به‌لام ئه‌وه‌ی جێگای سه‌رنج بوو،سه‌لماندنه‌كه‌ی Appel-Haken كه‌متر مایه‌ی خۆشحالی و پێشوازیلێكردن بوو هۆكاره‌كه‌یشی بۆ دوو شت ده‌گه‌رێته‌وه‌:-

  1. به‌شێك له‌ سه‌لماندنه‌كه‌ی ئه‌وه‌ دوو بیركاریزانه‌ پشتی به‌ كۆمپیوته‌ر ده‌به‌ست وه‌ نه‌ده‌كرا به‌ ده‌ست تاكیدی لێبكرێته‌وه‌.
  2. وه‌ ئه‌وه‌ به‌شه‌ی كه‌ ده‌توانرا به‌ ده‌ست پاسادانبكرێته‌وه‌ كه‌ راسته‌ تاڕاده‌یه‌كی زۆر ئالۆز و تاقه‌ت پرۆكێنه‌ر بوو، بۆیه‌ كه‌س نه‌یتوانی سه‌د ده‌ر سه‌د له‌وه‌لامه‌كه‌یان دڵینیابیت.

ئه‌م دوو هۆكاره‌ی سه‌ره‌وه‌ بووه‌ هاندانی ئه‌وه‌ی بیركاریزانه‌كان هه‌وڵی به‌ده‌ستهێنانی سه‌لماندنی نوێ بده‌ن كه‌ له‌رووی چێكدردنه‌وه‌( یان پاسادانه‌وه‌) ئاسانتر بیت.ماوه‌یه‌كی كه‌می برد تاوه‌كو سه‌لماندنێكی نوێ وه‌ ئه‌لگۆریزمێكی ئاسانتر بۆ ئه‌م بیردۆزه‌ خرایه‌ ڕوو.

یه‌كه‌م سه‌لماندن كه‌ جێگای قبوڵكردنی هه‌موو لایه‌ك بوو له‌ ساڵی 1996 له‌لایه‌ن Robertson بلاوكرایه‌وه‌ كه‌ كورتر و پووختر بوو سه‌لماندنێكی تریش به‌ جیا له‌ سالی 1998 له‌لایه‌ن تۆماس بلاوكرده‌وه‌. به‌لام دوای 8 ساڵ توانرا پیشانبدرێت كه‌ سه‌لماندنه‌كه‌ی رۆبرتسۆن ته‌واوه‌ وه‌ هیچ هه‌له‌یه‌كی تیادا نیه‌، كه‌ دیاره‌ ئه‌م چێكردنه‌وه‌ی سه‌لماندنه‌ له‌لایه‌ن دوو كه‌سه‌وه‌ بوو یه‌كیكیان (Gonthier ) له‌ ئینگلته‌ره‌ وه‌ ئه‌وه‌ی دیكه‌یان له‌ له‌ فه‌ره‌نسا وه‌ كه‌ Gonthier كاری بۆ كۆمپانیای مایكرۆسۆفت ده‌كرد.

گه‌ر سه‌رنج له‌ مێژووی سه‌لماندنی ئه‌م بیردۆزه‌ بده‌یت، ده‌بینیت بیركاریزانه‌كان ئه‌فزه‌ڵیه‌ت ئه‌ده‌ن به‌سه‌ر هه‌ندێك له‌ سه‌لماندنی بیردۆزێك وه‌ك له‌ هه‌ندێك سه‌لماندنی دیكه‌ كه‌ دیاره‌ هۆكاره‌كه‌ی زیاتر ته‌كنیكیه‌ بۆ نموونه‌ وه‌كو ئه‌وه‌ی بیردۆزی-چوار ڕه‌نگه‌ كه‌ سه‌لماندنه‌كه‌ی یه‌كه‌مجار كرداری پاسادانی زۆر زه‌حمه‌ت بوو، وه‌ هه‌ندێك جاری تر هۆكاره‌كه‌ جوانناسییه‌، وه‌كو ئه‌وه‌ی سه‌لماندنی ئیقلیدس بۆ ناڕێژه‌ییی بوونی ڕه‌گی دوو پیشانی داوه‌ له‌ ڕێگه‌ی دژیه‌كه‌وه‌( كۆنتراده‌كشن) كه‌ دیاره‌ له‌م بلۆگه‌ بادرێژی باسكراوه‌.

ئه‌م وێنه‌یه‌ كه‌له‌ خواره‌وه‌ پیشاندراوه‌،له‌ساڵی 1974 له‌ یه‌كی نیسان مارتن گاردنه‌ر (بیركاریناسی ته‌رفیهی بوو ) بلاوی كرده‌وه‌ كه‌ باسی له‌وه‌ كردوو ئه‌م نه‌خشه‌یه‌ له‌ 110 هه‌رێمی جیاواز پێكدیت وه‌ پێویستیت به‌ 5 ره‌نگ هه‌یه‌ بۆ ره‌نگردنی ، كه‌ دیاره‌ ئه‌مه‌یش دژی بیردۆزی چوار-ڕه‌نگه‌ وه‌ به‌ نموونه‌ی-پێچه‌وانه‌ ئه‌ژمارده‌كرێت ، به‌لام دیاره‌ فشه‌ی نیسان بوو بۆیه‌ كه‌س به‌جدی وه‌رینه‌گرت.

ئه‌م وێنه‌یه‌ ئاسان نیه‌ بۆ ڕه‌نگردن
ئه‌م وێنه‌یه‌ ئاسان نیه‌ بۆ ڕه‌نگردن

تێبینی:-

ئه‌م پۆسته‌ به‌ فورسه‌ت ده‌زانم كه‌ باس له‌وه‌ بكه‌م كه‌ بیركاریزانه‌كان چۆن له‌ بیردۆزی له‌م شێوه‌یه‌ ده‌روانن؟ گه‌ر سه‌رنج بده‌یت ئه‌م بیردۆزه‌ سه‌ره‌تا له‌ كێشه‌یه‌كی ژیانی ڕۆژانه‌وه‌ یاخود بابه‌تێكی جوگرافیاوه‌ دروست بووه‌، به‌لام دواتر كه‌ بوو خه‌می بیركاریزانه‌كان ئه‌و پرسیاره‌كه‌ گۆرا وه‌ شێوه‌ی ئه‌بستراكتی وه‌رگرت،مه‌به‌ستمان له‌ ئه‌بستراكت لێره‌ ئه‌وه‌یه‌ كه‌ گه‌ر سه‌یری شێوازی ئێشكردنی بیركاریزانه‌كان بكه‌یت له‌سه‌ر ئه‌م پرسیاره‌ ئه‌وه‌ زه‌حمه‌ته‌ بروابكه‌یت كه‌ ئه‌مه‌ ئه‌و پرسیاره‌یه‌، بۆ ئه‌وه‌ی له‌م قسه‌یه‌ی سه‌ره‌وه‌ زیاتر حالیببیت، وه‌كو نوته‌ی مۆسیقای میوزیكژه‌نه‌كان وایه‌ كه‌ ته‌نها خۆیان لیێ تێده‌گه‌ن، به‌لام ئه‌وه‌ی راستیبیت ئه‌وه‌ی بیركاریزانه‌كان له‌وه‌دا جیاوازه‌ كه‌ ته‌نها چه‌ند كه‌سێك كه‌ له‌و بواره‌دا كارده‌كه‌ن لێی حالی ده‌بن. له‌ خواره‌وه‌ ئه‌م قسانه‌ به‌ وێنه‌ روونده‌كه‌ینه‌وه‌.

گه‌ر سه‌یرێكی وێنه‌كه‌ی لای چه‌پ بكه‌یت ئه‌وا نه‌خشه‌یه‌كه‌ ره‌نگراوه‌ به‌ چوار ڕه‌نگ، به‌لام ئه‌وه‌ی لای راست بكه‌یت هه‌مان وێنه‌یه‌ به‌لام به‌شێوه‌ی نووك و لێوار كه‌ ئه‌مه‌یان بیركاریزانه‌كان به‌م شێوه‌یه‌ كاری له‌سه‌ر ده‌كه‌ن، واته‌ هه‌ردوو وێنه‌كه‌ یه‌كشتن به‌لام ئه‌وه‌ی لای چه‌پ بۆ بیركاریزان مانایه‌كی تری هه‌یه‌ وه‌ ئاسانتر به‌ده‌سته‌وه‌ دێت چونكه‌ ئێستا ده‌توانرێت سه‌رجه‌م ئه‌م ئامرازانه‌ی كه‌ تایبه‌ته‌ به‌م  جۆره‌ وێنانه‌ به‌كاربهێنیت، وه‌ ئه‌و لقه‌ی بیركاری كه‌ تایبه‌ته‌  به‌م جۆره‌ وێنانه‌ ده‌وترێت تیۆری گراف، له‌ هه‌ندێك له‌ زانكۆكانی كوردستان له‌ قۆناغه‌كانی كۆتاییدا ده‌خوێنرێت.

graph colouring

چالاكی:

گه‌ر به‌رێزت مامۆستایت،یاخود به‌رێزت باوكیت یان كه‌سێكی گه‌نجێیت ئه‌وه‌ ئه‌م چالاكیانه‌ پێشكه‌شه‌ به‌تۆ، سه‌ره‌تا به‌ كۆمه‌ڵێك وێنه‌ی ئاسان ده‌بیپێده‌كه‌ین، ده‌توانیت ئه‌م وێنانه‌ چاپ بكه‌یت یان ده‌توانیت له‌سه‌ر كۆمپیته‌ره‌كه‌ت یان مۆبایله‌كه‌ت شیكاری بكه‌یت،

دووباره‌ مه‌رجه‌كه‌ ئه‌وه‌ی نابێت هیچ دوو هه‌رێمێكی جیاوازی ته‌نیش یه‌كتر هه‌مان ره‌نگیان هه‌بیت، دیاره‌ گه‌ر هاتوو دوو هه‌رێم ته‌نها له‌ خالێكدا هاوبه‌شبوون ئه‌وا ئه‌و خاڵه‌ حسابی بۆ ناكرێت و ئه‌و دووهه‌رێمه‌ به‌ دوو جیا ته‌ماشاده‌كرێت و ده‌كرێت هه‌مان ڕه‌نگیان هه‌بێت.

coloring-1coloring-3

coloring-7

 دوا سه‌رنج:- ئه‌م بیردۆزه‌ هه‌لێكی باشه‌ تا واله‌ كه‌سانه‌ بكرێت كه‌له‌به‌شه‌ ئه‌ده‌بیه‌كان ده‌خوێنن كه‌ حه‌زیان بۆ بیركاری بجوێلێنیرێت.

سه‌رچاوه‌:-

http://people.math.gatech.edu/~thomas/FC/fourcolor.html

http://mathworld.wolfram.com/Four-ColorTheorem.html

http://nrich.maths.org/6291

Advertisements

وەڵامێک بنووسە

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / گۆڕین )

Twitter picture

You are commenting using your Twitter account. Log Out / گۆڕین )

Facebook photo

You are commenting using your Facebook account. Log Out / گۆڕین )

Google+ photo

You are commenting using your Google+ account. Log Out / گۆڕین )

Connecting to %s