0:04 السلام عليكم ورحمة الله وبركاته كل عام وأنتم بخير بحلول فصل الدراسي الجديد في مادة مواضيع مختارة والتي يطلق عليها Selected Topics في هذا المصار سنشرح لكم مادة Graph Theory الكتب المقررة في هذا المصاق حسب الأهمية كالتالي الكتاب الأول طبعا ترتيب الكتب حسب أهمية هذا الكتاب الأول
0:53 هو Introduction to Discret Mathematics James Bradley Edison Wisely Publishing Company الكتاب الثاني هو Discret Mathematics and its Application كينث أتش روزن هو أمسي غروهل إيكليو دينغ ثري وهي ديستريف ماثماتيكس ماك ميلان بابلشين كامبني نيويورك وشركة أخرى اللي هي كولينير ماك ميلان بابلشين كامبني اللي مقار لها لندن طبعا في كتاب موجود في المكتبة الطالب اللي هو عبارة عن دمج بين
1:40 الكتب الثلاثة الموجودة معنا بإمكانكوا تخذوه من المكتب أو أنه من أحد زملاتكوا السابقين بداية خلينا نشوف نشأة هذا العلم أي علم الـ Graph Theory نشأ هذا العلم في القرن الثامن عشر إثر مشكلة سميت بمشكلة جسر كونزباك عبر
2:28 بريغل ريفر أو نهر البريغل في هذا المكان أو في ذلك الوقت كان رياضة المشي هي رياضة رائجة والمشكلة كانت أنه كيفية ترسم طريق للمشاة بحيث يكون العبور من جميع الجسور مرة واحدة والرجوع من نفس الجهة يعني في عندي هنا هذا نهر طبعا هذه ضفة النهر وهي الضفة الأخرى طبعا هنا الجسور تؤدي إلى جزيرتين طبعا في
3:17 عندي ثلاثة أربعة خمس ستة سبع جسور وجزيرتين المراد أنه لو دخلنا من الجهة هذا نخرج من نفس الجهة ولو دخلنا من الجهة الأخرى برضو نخرج من نفس الجهة تم استدعاء العديد من الغيابيين في ذلك الوقت وصلوا إلى طريق مسدود فاستدعوا عالم من أحد أهم مشاهير الرياضيات في ذلك الوقت اللي هو ما يسمى بليون هارد آيلر
4:05 عندما بحث آيلر في هذه الخريطة لحل المشكلة المرادة وصل إلى نتيجة أنه لا يمكن ذلك إلا بوضع جسور إضافية ومن هنا بدأ علم الـ Graph Theory طبعا الرسم هذا بتتطبح عندكم لاحقا وهي عملية ترانسفير لما هو موجود هنا على شكل الـ Graph بس بشكل سريع الـ Vs هنا هي رموز لـ Vertices أو رؤوس هناك عندي مثلا لو عملنا هذه الجزيرة الأولى V4 والجزيرة
4:53 الثانية كV2 وV1 تمثل الضفة من هذا الاتجاه اليابسة وV3 اليابسة من الجانب الآخر فلاحظوا هنا أنه الجزيرة الموجودة عندها فيها طريق على الضفة الخارجية ومنها كمان مرة وعلى الجزيرة الثانية فبالتالي على V1 وV3 اللي هم ضفي النهر والهي من V4 لV2 اللي هي الجزيرة الجسر اللي من بين الجزرتين فبالتالي الثلاث جسور اه اه اه اه اه اه الجزيرة الموجودة عندي هان فيه الجسر اللي في فور وفيه جسرين
5:39 بطلعن عالضفة اللي فوق وجسرين بنزلن عالضفة اللي تحت فسميا رؤوس وحواف التي ستتضح لاحقاً طبعاً لكي نفهم العلم هذا بلزمنا بعض التعريف فهو بعض التعريف لو جئنا إلى تعريف أول وهو تعريف الجراف غراف جي عبارة عن VE
6:26 اللي نقصد فيها هان اللي هو G is a set of vertices and a set of edges V اللي نقصد فيها مجموعة vertices و E مجموعة edges فبالتالي غراف جي is an empty set V بمعنى هو مجموعة غير خالية من ال vertices أو الرؤوس و ومجموعة من الحواف بمعنى بحيث أن كل حافة لها علاقة بزوج من الرؤوس
7:13 تعريف اتنين اللي هي two vertices زي vertex V1 و vertex V2 E1. هنالنقصد فيها edge. حافة بين vertex V1 و V2. فبالتالي definition بقول هنالنه او التعريف انه two vertices are called adjacent. فبالتالي هنا نقصد تعريف الadjacency. فبالتالي two vertices are called adjacent if there is an edge E between them. فبالتالي illustration. ال vertices v1 و v2 are adjacent. بمعنى يوجد edge بينهم فبالتالي adjacent. بينما v2 و v4 are not
8:04 adjacent. لانه في الشي edge مباشرة او حافة تربط v2 بال v4 مباشرة فبالتالي they are not فهنا تعريف الاجسنسي نقصد بالاجسنسي هنا أو two matrices are adjacent if there is an edge between then فهي علاقة الاجسنسي علاقة vertex by vertex عبر edge معين نشوف تعريف آخر
8:51 إذا كانت تعريف ما يسمى بالإنسدانسي إنسدانسي اللي هي المقصود فيها علاقة فارتكس بأج العلاقة فارتكس بأج العلاقة فارتكس بأج العلاقة فارتكس بأج العلاقة فارتكس بأج العلاقة فارتكس بأج العلاقة فارتكس بأج عبر أج معين يعني مثلا V1 V2 لما قلنا عنهم adjacent بمعنى يوجد edge تربطهم لكن عندما نقول incident and a vertex is incident on V بمعنى هي
9:37 تقى على ال edge E فبالتالي V1 is incident on E1 وال V2 is incident on both E1 and E1 فبالتالي هن برجع بأكد اللي هي الاجسنسي والانسدنسي الاجسنسي الاجسنسي هي علاقة ذيرتكس بذيرتكس عبر اج فنقول أنه اذا وجد اج بربطهم أما عندما نقول أنه Vertex is incident on an edge نقصد أنها هذا الedge بتصل هذا الـ Vertex أو الـ Vertex
10:26 تقع على هذا الـ Edge تعريف آخر the number of edges incident on a vertex v here I am saying that the answer is small v small v we can say vertex, not vertex set the number of edges incident on a vertex is called the degree of that vertex and is denoted by
11:13 V يعني degree of the vertex V فبالتالي في الغراف البسيء المرسوم عندي هان degree of the vertex V1 is 1 بمعنى إدج واحد تصل لهذا ال vertex degree V3 again 1 بينما degree V2 عبارة عن 2 ليش لأنه قلنا أنه الرقم 2 يمثل الدقري للفرتكس والدقري للفرتكس قلنا هو عبارة عن إيش هو عبارة عن number of edges incident on this vertex بمعنى أنه عدد ال edges اللي واصلة لهذا
11:59 الفرتكس فبالتالي الدقري للفيتو هي عبارة عن 1 2 فبالتالي as E1 and E2 are incident on تعريف آخر وهنا تعريف ما يسمى بلوب بمعنى هاي بطلع عندي edge وبترجع ثاني لنفس البرتكس هذا بنسميه لوب فبالتالي a lobe is an edge هي عبارة عن edge لأن
12:55 المقصد بـ identical لكن لو جينا نقول ما هو الدقري للفاتيكس في اثنين لأنه يخرج ويرجع إليها ثاني فبالتالي هنا as two edges بمعنى فلاحظوا هنا فيما سبق يعني مثلا edge e1 ابتدينا one degree to one degree to one degree to one edge e2 one to v3 one to v2 بمعنى each edge contributes to to the degree of the edge
13:43 بمعنى كل اج بدنا اتنين ديجريز اللي واحد هان وواحد هان لهذا واحد هان وواحد هان فبالتالي اللوب هان هي عبارة عن اج فبالتالي اللي بدنا طولة ديجريز فبالتالي على تساس identical vertex اللي هي same vertex فبالتالي هنا degree for this vertex is two طب تعريف آخر لاحظوا نحن هنا نشتغل مكونات لغرافي لحد ما فـ two edges are parallel لاحظوا هنا الرسمي قبل ما نقرأ التعريف عندي هنا two vertices v1 و v2 في عندي
14:33 Edge E1 و Edge E2 for the same vertices. فهنا نسمي E1 و E2 parallel متوازيات. ف2 edges E1 E2 are parallel أو are set to be parallel. بنسميهم متوازيات. إذا كانوا تعلقون بشكل مختلف من الزوج ففي هذا الحالي نقول إنه الـ edge E1 و E2 يكون مختلف طبعا
15:19 الـ V1 و V2 في هذا الحالي لو أرجعنا التعريف السابق أجن تعريف لما يسمى بسبغراف السب هو مصطلح متعارف عليه بالنسبة لطلاب الرياضيات اللي هي زي ما أخذت حاجة اسمها سبست مجموعة جزئية في
16:05 عندي هنا حاجة اسمها سبغراف بمعنى هو غراف جزئي من غراف أكبر منه بمعنى لو كان جي اللي هو في إي بيا غراف Then we see that G' is a subgraph of GFV' is a subset of V and E' is a subset of E. Toadih للsubgraph, here I have two graphs G1 and G2. لاحظ هنا جي 2 أخذنا جزء من الجراف الأول هو عبر ثري فيرتيسيز وتو إجز أخذنا فقط فبالتالي
16:54 الجراف جي 1 إذا فارتك ست وإجز ست بحيث أن الفارتك ست في عبارة عن في وان في وان في وي ثري في فور والإجز ست إي وان إي تو إي ثري إي فور طب نشوف الجراف جي تو الو الفرتكسة في V' والجسة عبارة عن E' الفرتكسة هي عبارة عن V1 V2 V3 والجسة عبارة عن E1 E2 فلو لاحظنا هنا بنلاقي انه V' is a subset of V والE' subset of E بهاي الحالة بنقدر نقول انه الـ Graph G2 is a subgraph of G1
17:46 أو جراف جزئي من الجراف G1 تعريف آخر تعريف ما يسمى بمالتيغراف مالتيغراف المقصود فيه هو جراف يحتوي على ما أعلى له ما يسمى بـ Parallel edges ولا مانع من وجود لهو Loops هذا بنسميها Loop إذا ما تذكرين في التعريف السابقة وهذول E1 و E2 عبارة عن Parallel edges فبالتالي تعريف المالتيغراف
18:37 إيش هو؟ A graph with Parallel edges set to be multi graph. دي معنى الـ graph لو وجد فيه parallel edges دغري بنسميه multi graph. مدام أجا تعريف multi graph بيجي عنا ما يسمى بتعريف حاجة اسمها simple graph. simple graph اللي هي graph بسيط. simple graph هنا هو عبارة عن graph بحيث لا يحتوي لا على parallel edges ولا على loops لا parallel edges ولا loops فبالتالي
19:22 a graph G equals to VE with neither parallel edges nor loops بمعنى بدون parallel edges بدون edges متوازية ولا لوبز زي E5 في هذا الحال بنسمي الـ Graph is called Assemble Graph الـ Graph في هذا الحال بنسميه Symbol Graph في عندي هنا ذاكر مثال لا Symbol Graph عندي Vertices V1 V2 V3 و Edges E1 E2 E3 لاحظوا هنا أنه لا في لوبز ولا في parallel edges فبالتالي هذا الـ graph عبارة عن sample
20:11 graph نستكمل العمل في المحاضرة القادمة والسلام عليكم ورحمة الله وبركاته
