في نظرية الرسم البياني ، الرسم البياني هو بنية مجردة تمثل مجموعة من الكائنات مع الروابط الموجودة بين هذه الكائنات. تسمى التجريدات الرياضية للكائنات عقد (أو زوايا ) الرسم البياني. تسمى الاتصالات الزوجية بين العقد بالحواف (أحيانًا أقواس أيضًا ). يمكن توجيه الحواف أو عدم توجيهها . غالبًا ما يتم رسم الرسوم البيانية من خلال تمثيل العقد بالنقاط والحواف مع الخطوط. ^[1]

الهيكل التخطيطي لشجرة العائلة

مخطط مترو أنفاق فيينا

الأمثلة التوضيحية للرسوم البيانية هي شجرة العائلة أو شبكة مترو أنفاق المدينة (انظر الرسوم التوضيحية). في شجرة العائلة ، تمثل كل عقدة أحد أفراد العائلة وكل حافة عبارة عن اتصال بين الوالد والطفل. في شبكة مترو الأنفاق ، تمثل كل عقدة محطة مترو أنفاق وتمثل كل حافة اتصال قطار مباشر بين محطتين.

أنواع الرسوم البيانية

رسم بياني غير موجه

في الرسوم البيانية غير الموجهة ، يتم الإشارة إلى الروابط بين العقد بالحواف . الحواف ليس لها اتجاه. يمكن اجتياز كل حافة في كلا الاتجاهين.

الرسم البياني الموجه (Digraph)

في Digraphs ، يتم الإشارة إلى الحواف بواسطة الأسهم بدلاً من الخطوط ، حيث يشير السهم من بدايتها إلى عقدة نهايتها. يوضح هذا أنه لا يمكن اجتياز كل حافة في الرسم البياني إلا في اتجاه واحد. ^[2]

شجرة

في نظرية الرسم البياني ، الشجرة هي نوع خاص من الرسم البياني متصل ولا يحتوي على مسارات مغلقة ، أي دورات بطول أكبر من أو تساوي 3. بالنسبة لجميع الأشجار ، من الواضح أن عدد الرؤوس أكبر من عدد الأضلاع بمقدار 1.

للأشجار العديد من الاستخدامات العملية ، وأبرزها في علوم الكمبيوتر . يتم برمجة العديد من الخوارزميات باستخدام الأشجار . على سبيل المثال ، يمكن اجتياز الشبكات أو شبكات النقل أو شبكات المرافق بفاعلية من خلال البحث ذي النطاق الواسع أو البحث العميق أولاً. في مجال الذكاء الاصطناعي والألعاب الإستراتيجية ، يعد بحث alpha-beta مهمًا. يعتمد على أشجار البحث .

متعدد الرسم البياني

الرسم البياني المتعدد: يتم تصور الحواف المتعددة بواسطة حافة مرجحة

في ما يسمى بالرسومات المتعددة ، يمكن أيضًا توصيل عقدتين بواسطة حواف متعددة ^[3] ، وهو أمر غير مسموح به في الرسوم البيانية البسيطة . بالإضافة إلى ذلك ، يُسمح للرسومات المتعددة أن تحتوي على حلقات: حواف تؤدي إلى نفس الرأس الذي نشأت منه. ^[1]

إذا كانت العقد متصلة بعدة حواف ^[3] ، فغالبًا ما يتم رسم حافة واحدة فقط ويتم كتابة عدد الحواف بين هاتين العقدتين كوزن الحافة على حافة واحدة. في المثال يوجد 60 حافة بين العقدتين A و D. بدلاً من رسم جميع الحواف الستين ، يتم رسم حافة بوزن الحافة 60.

رسم بياني مستو

الرسم البياني المستوي هو رسم بياني يمكن رسمه على مستوى ، مع نقاط للعقد وخطوط للحواف ، بحيث لا تتقاطع أي حواف. كل رسم بياني مستو له رسم بياني مزدوج . هذا رسم بياني حيث يرتبط كل وجه من وجوه الرسم البياني بعقدة تقع داخل ذلك الوجه ، والعكس صحيح. دائمًا ما تكون ثنائية الرسوم البيانية المستوية متبادلة ، أي أن الرسم البياني المزدوج للرسم البياني المزدوج لأي رسم بياني مستوٍ هو الرسم البياني المستوي الأصلي.

تنطبق نظرية أويلر متعدد السطوح على الرسوم البيانية المستوية ، وغالبًا ما يتم تمثيلها باستخدام المعادلة ${\ displaystyle E-K + F = 2}$

hypergraph

في hypergraphs ، لا تربط الحافة (تسمى أيضًا hyperedge ) عقدتين فقط ، ولكن عدة عقدتين في نفس الوقت. على سبيل المثال ، يمكن تمثيل الرسوم البيانية الفائقة بعدة رسوم بيانية مستوية مع فهرسة الحافة . يتم رسم الرسوم البيانية ذات الحواف القليلة (تسمى الرسوم البيانية المتفرقة ) عن طريق رسم مجموعة من النقاط المقابلة للرؤوس ، ثم يتم إحاطة النقاط التي تنتمي إلى hyperedge بخط مغلق ، وهو بالتالي المجموعة الفرعيةمن العقد التي تنتمي إليها داخل جميع العقد. في حالة الرسوم البيانية ذات الحواف المتعددة ، فإن هذا التمثيل سرعان ما يصبح محيرًا. من الأقل بديهية ، ولكن أكثر وضوحًا ، تمثيل الرسم البياني الفائق باعتباره رسمًا بيانيًا فرعيًا ثنائي الأجزاء ، حيث تتوافق إحدى المجموعتين ذات القسمين مع عُقد الرسم البياني والأخرى ثنائية القسم على الحواف المفرطة للرسم البياني. ثم ترمز الحواف بين هاتين المجموعتين من القسمين إلى انتماء العقد إلى الحواف المفرطة.

يعتمد مشروع الفيزياء لستيفن ولفرام (انظر أيضًا: Wolfram Research and Mathematica ) لشرح أساسيات الفيزياء ، من بين أشياء أخرى ، على فضاء القواعد فوق الرسوم البيانية الزائدة: "وعلى الأقل بالنسبة لتقريب معين يمكننا بعد ذلك أن نقول أن الطاقة يرتبط بالنشاط في الرسم البياني ، الذي ينشر المعلومات عبر الزمن ، بينما الزخم مرتبط بالنشاط ، الذي ينشر المعلومات في الفضاء. " ^[4]

تعريفات

الرسم البياني هو زوج مرتب ، يشير إلى مجموعة من العقد ( الرؤوس / الرؤوس ، تسمى أحيانًا الزوايا ) ومجموعة من الحواف ( الحافة / الحواف ، تسمى أحيانًا الأقواس ). اين هو ${\ displaystyle G}$ ${\ displaystyle (V، E)}$${\ displaystyle V}$ ${\ displaystyle E}$ ${\ displaystyle E}$

• الرسوم البيانية غير الموجهة بدون حواف متعددة مجموعة فرعية من كل المجموعات الفرعية المكونة من عنصرين من ^[1] ،${\ displaystyle V}$
• الرسوم البيانية الموجهة بدون حواف متعددة مجموعة فرعية من جميع الأزواج (i ، j) الناتجة عن المنتج الديكارتي ، ^[5]${\ displaystyle V \ times V}$
• الرسوم البيانية غير الموجهة مع حواف متعددة مدمجة ، مجموعة متعددة على مجموعة من جميع المجموعات الفرعية المكونة من عنصرين ، أي وظيفة ،${\ displaystyle W}$${\ displaystyle V}$ ${\ displaystyle E \ Colon W \ to \ mathbb {N} _ {0}}$
• الرسوم البيانية الموجهة مع حواف متعددة مدمجة على المنتج الديكارتي ، أي دالة${\ displaystyle V \ times V}$${\ displaystyle E \ Colon V \ times V \ to \ mathbb {N} _ {0}}$
• الرسوم البيانية الموجهة ذات الحواف المتعددة في حد ذاتها ، والتي تعتبر عناصرها بمثابة حواف بمساعدة وظيفتين تقومان بتعيين رأس المصدر والوجهة للعناصر (مثل هذا الرسم البياني هو نفسه الممر ، مع فئة يمكن التحكم فيها إلى حد ما مع اثنين الأشياء واثنين من الأسهم الممتازة)${\ displaystyle \ mathrm {src}، \ mathrm {tgt} \ colon E \ to V}$ ${\ displaystyle G \ Colon {\ mathcal {G}} \ to \ mathbf {Set}}$${\ displaystyle {\ mathcal {G}}}$${\ displaystyle {\ mathcal {G}} = \ {V {\ stackrel {\ mathrm {src}} {\ longleftarrow}} E {\ stackrel {\ mathrm {tgt}} {\ longrightarrow}} V \}}$
• Hypergraphs هي مجموعة فرعية من مجموعة الطاقة من . ^[1]${\ displaystyle V}$

رسم بياني غير موجه بدون حواف متعددة

رسم بياني موجه بدون حواف متعددة

رسم بياني غير موجه ذو حواف متعددة

رسم بياني موجه بحواف متعددة

عادة ما يتم حذف الإضافة "بدون حواف متعددة" وتسمى الرسوم البيانية ذات الحواف المتعددة بالرسم المتعدد . علاوة على ذلك ، عادةً ما يتم حذف السمة "غير موجه" ويتم تمييز الرسوم البيانية الموجهة صراحةً فقط. غالبًا ما تسمى الرسوم البيانية غير الموجهة بدون حواف متعددة عادية أو بسيطة . اسم آخر للرسوم البيانية الموجهة هو digraph (الرسم البياني الموجه).

الشروط المشتقة

بدلاً من تحديد مجموعة الرؤوس والحواف للرسم البياني بالرموز ، يمكن للمرء أيضًا تحديد الخرائط العامة وتعيين الرسم البياني لمجموعة الرؤوس أو الحواف الخاصة به. للحصول على رسمين بيانيين والدلالة و وكذلك و . ${\ displaystyle G}$${\ displaystyle V}$${\ displaystyle E}$ ${\ displaystyle V}$${\ displaystyle E}$${\ displaystyle G_ {1} = (V_ {1}، E_ {1})}$${\ displaystyle G_ {2} = (V_ {2}، E_ {2})}$${\displaystyle V(G_{1}):=V_{1}}$${\displaystyle E(G_{1}):=E_{1}}$${\displaystyle V(G_{2})=V_{2}}$${\displaystyle E(G_{2})=E_{2}}$

يتم قبول الغموض مع هذا الترميز ، على الرغم من أن التعيينات تمثل شيئًا آخر غير العقدة ومجموعة الحافة المرتبطة بها. كمصطلح ، من المستحسن الإشارة إلى مجموعة العقد أو الحواف مع أو بدون وسيطة ، أو الإشارة إلى التعيينات المحددة باستخدام وسيطة. ${\displaystyle V(G)=V}$${\displaystyle E(G)=E}$${\displaystyle V}$${\displaystyle E}$${\displaystyle V}$${\displaystyle E}$

إذا كان الرسم البياني ، فإن المرء يقول بشكل عام أنه عقدة أو رأس ، إذا كان ينتمي إلى . يشار إلى الحواف أيضًا باسم ${\displaystyle G}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle V(G)}$${\displaystyle e\in E(G)}$

• الحافة غير الموجهة لـ if هي رسم بياني غير موجه.${\displaystyle G}$${\displaystyle G}$
• إذا كانت الحافة الموجهة هي رسم بياني موجه.${\displaystyle G}$${\displaystyle G}$
• Hyperedge من إذا هو hypergraph.${\displaystyle G}$${\displaystyle G}$

في الحافة غير الموجهة ، نشير إلى العقد النهائي لـ . في الحافة الموجهة نسمي عقدة البداية ونقطة النهاية لـ . ${\displaystyle e=\lbrace v,w\rbrace }$${\displaystyle v}$${\displaystyle w}$${\displaystyle e}$${\displaystyle e=(v,w)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle e}$

في multigraphs يدل على تعدد . إذا كان الأمر كذلك ، يتحدث المرء عن حواف متعددة أو متعددة . ${\displaystyle E(G)(e)}$${\displaystyle e}$${\displaystyle E(G)(e)>1}$

إذا كانت الحافة في الرسوم البيانية الموجهة لها شكل ، فإنها تسمى حلقة . إذا كانت الحلقة في الرسم البياني المتعدد هي أيضًا متعددة الحواف ، فإنها تسمى حلقة متعددة . تسمى الرسوم البيانية الموجهة بدون حلقات بدون حلقات أو حلقة خالية . ${\displaystyle e}$${\displaystyle (v,v)}$${\displaystyle e}$${\displaystyle G}$

عدد العقد في الرسم البياني هو عدد عقده ، وعدد الحواف هو عدد حوافه (في الرسم البياني ، مجموع واحد على تعدد الحواف). ${\displaystyle n(G)=\vert V(G)\vert }$${\displaystyle G}$ ${\displaystyle m(G)=\vert E(G)\vert }$

تسمى عقدتان متجاورتان إذا كانت الحافة تربطهما.

حالات خاصة

إذا كانت الحافة تربط عقدتين في رسم بياني موجه ، وكانت الحافة تربط نفس العقد في الاتجاه المعاكس ، فيمكن للمرء أيضًا اعتبارهما معًا كحافة غير موجهة داخل الرسم البياني الموجه. في حالة وجود حواف متعددة ، يجب أن تتطابق تعدد الحواف. ${\displaystyle e_{1}}$${\displaystyle e_{2}}$

إذا كانت كل حافة في الرسم البياني الموجه لها مثل هذه الحافة المعاكسة في الرسم البياني ، فهذا يمثل رسمًا بيانيًا متماثلًا .

يسمى الرسم البياني الذي تكون مجموعة عقده محدودة بالرسم البياني المحدود . في المقابل ، يُطلق على الرسم البياني الذي تكون مجموعة العقد فيه لانهائية اسم الرسم البياني اللانهائي . عادة ، ينظر المرء فقط إلى الرسوم البيانية المحدودة ، وبالتالي يتجاهل السمة "محدودة" ، بينما يتم تمييز الرسوم البيانية اللانهائية بشكل صريح.

الرسوم البيانية الفرعية والمسارات والدورات

رسم بياني موجه مع دورة

رسم بياني موجه بدون دورة

يحتوي الرسم البياني الفرعي للرسم البياني فقط على العقد والحواف المضمنة أيضًا في. يحتوي الرسم البياني الفرعي المستحث من مجموعة العقدة U على العقد في U وجميع الحواف في G بين هذه العقد. ${\displaystyle G'}$${\displaystyle G}$${\displaystyle G}$

يُطلق على سلسلة من العقد المتميزة الزوجية ، حيث ترتبط العقد المتتالية وفي الرسم البياني بواسطة حافة ، مسارًا ، وأحيانًا مسار أيضًا . إذا كانت هذه هي العقدة المزدوجة الوحيدة ، فإنها تسمى دورة أو دائرة . يسمى تسلسل العقد المجاورة التي يُسمح فيها للعقد بالتكرار تسلسل الحافة . أحيانًا يتم تعريف مصطلحات الطريق والمسار وتسلسل الحافة والدائرة والدورة بشكل مختلف في الأدبيات. ${\displaystyle v_{1},\ldots ,v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i+1}}$${\displaystyle v_{1}=v_{n}}$

إذا كان الرسم البياني الموجه لا يحتوي على دورة ، فإنه يسمى لا دوري أو خالي من الدورة - أي رسم بياني لا دوري موجه ( DAG ، رسم بياني لا دوري موجه ). يمكن توسيع مثل هذا الرسم البياني إلى ترتيب جزئي (محدود ومنفصل) عن طريق إضافة جميع الحواف التي لها نفس عقد البداية والنهاية مثل المسارات ، أي تقصير الانعطافات عبر الحواف الأخرى إلى عقدة الوجهة . تسمى هذه العملية بتشكيل الإغلاق الانتقالي . مخطط Hasse هو رسم بياني لا دوري موجه حيث ، بموجب قانون العبور ،تم حذف الحواف الضمنية ( تقليل متعد ).

العمليات الأساسية

عند فحص خصائص الرسم البياني ، غالبًا ما يحدث أنه يتعين عليك تطبيق عمليات بسيطة على الرسوم البيانية حتى تتمكن من الكتابة بشكل مضغوط قدر الإمكان وبالتالي يسهل فهمها. يتم تطبيق العمليات المعتادة لنظرية المجموعات (الاتحاد والتقاطع والاختلاف والمكمل) بشكل متكرر بشكل خاص على مجموعات من العقد أو حواف الرسوم البيانية ، بحيث يتم تحديدها مباشرة على الرسوم البيانية.

هي والرسوم البيانية من نفس النوع ، لذلك يشار إليها ${\displaystyle G_{1}=(V_{1},E_{1})}$${\displaystyle G_{2}=(V_{2},E_{2})}$

• ${\displaystyle G_{1}+G_{2}}$الرسم البياني الناتج عن دمج مجموعة العُقد والحواف ،
• ${\displaystyle G_{1}-E_{2}}$الرسم البياني الناتج عن الطرح من مجموعة حافة و${\displaystyle E_{2}}$${\displaystyle G_{1}}$
• ${\displaystyle G_{1}-V_{2}}$الرسم البياني الناتج عن الطرح من مجموعة الرؤوس وإزالة جميع الحواف التي تحتوي على الرؤوس من .${\displaystyle V_{2}}$${\displaystyle G_{1}}$${\displaystyle V_{2}}$

لاحظ التعاريف المختلفة لمصطلح الاتحاد والاختلاف للمجموعات والمجموعات المتعددة . أنت تكتب أيضًا بشكل مختصر

• ${\displaystyle G_{1}+E_{2}}$، إذا كانت مجموعة فرعية من ،${\displaystyle V_{2}}$${\displaystyle V_{1}}$
• ${\displaystyle G_{1}+V_{2}}$، إذا كانت فارغة أو مجموعة فرعية من ،${\displaystyle E_{2}}$${\displaystyle E_{1}}$
• ${\displaystyle G_{1}+\{v,w\}}$، إذا ،${\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}$
• ${\displaystyle G_{1}+v}$، إذا ،${\displaystyle G_{2}=(\{v\},\{\})}$
• ${\displaystyle G_{1}-\{v,w\}}$، إذا و${\displaystyle E_{2}=\{\{v,w\}\}}$
• ${\displaystyle G_{1}-v}$إذا .${\displaystyle V_{2}=\{v\}}$

يعد تقلص الحافة وتشكيل الرسم البياني التكميلي عمليات أساسية أخرى.

ملاحظات

الرسوم البيانية غير الموجهة بدون حواف متعددة هي حالات خاصة للرسوم البيانية التشعبية. الرسوم البيانية المتعددة التي لا تحدث فيها حواف متعددة لا تكافئ رسمياً الرسوم البيانية بدون حواف متعددة ، لكنها مكافئة وصفيًا ، وهذا هو سبب تسميتها أيضًا بالرسوم البيانية بدون حواف متعددة. هناك تعيين حيوي بين المتغيرين. بهذا المعنى ، فإن الرسوم البيانية بدون حواف متعددة هي حالات خاصة للرسوم البيانية ذات الحواف المتعددة. وبالمثل ، فإن الرسوم البيانية غير الموجهة هي ، بمعنى ما ، حالات خاصة من الرسوم البيانية الموجهة. إذا كان الرسم البياني الموجه متماثلًا وبدون حلقات ، فإنه يسمى أيضًا غير موجه لأنه يوجد أيضًا تخصيص بسيط واحد لواحد بين المتغيرين (انظر أيضًا مصفوفة التقارب ).

بالطبع ، يمكن أيضًا تحديد الرسوم البيانية غير الموجهة ذات الحلقات ، حيث من المحتمل أن يتم تعريفها بسهولة على أنها حالات خاصة (رسمية) للرسوم البيانية الموجهة ويتم استبعاد حالة التكرار. ومع ذلك ، نادرًا ما تكون مثل هذه الرسوم البيانية موضوع اعتبارات في نظرية الرسم البياني.

أكثر أنواع الرسوم البيانية شيوعًا هي الرسوم البيانية الموجهة ذات الحواف المتعددة. يمكن بعد ذلك عرض كل نوع رسم بياني محدد أعلاه كحالة خاصة لهذا النوع. ومع ذلك ، نادرًا ما تكون مثل هذه الرسوم البيانية موضوع اعتبارات في نظرية الرسم البياني ، وهذا هو سبب عدم شرحها بمزيد من التفاصيل هنا.

إذا كانت الرسوم البيانية بمثابة تمثيل لحقيقة ، فإن الخوارزميات مطلوبة لرسم الرسم البياني . استمر هذا التخصص في علوم الكمبيوتر في التطور في السنوات الأخيرة ويوفر حلولًا لتصورات مختلفة تستند إلى الرسوم البيانية.

ملحقات

يمكن استكمال الرسوم البيانية بخصائص أو معلومات إضافية.

الرسوم البيانية الملونة

يتم الحصول على امتداد للرسوم البيانية للرسوم البيانية ذات لون العقدة من خلال إكمال المجموعة لتشكيل ثلاثية . هو تعيين من داخل مجموعة الأعداد الطبيعية . من الواضح أن كل عقدة لها لون. ${\displaystyle G=(V,E)}$${\displaystyle (V,E)}$${\displaystyle (V,E,f)}$${\displaystyle f}$${\displaystyle V}$

بدلاً من العقد ، يمكن للمرء أيضًا تلوين الحواف في الرسوم البيانية بدون حواف متعددة وفي الرسوم البيانية العالية ثم التحدث عن رسم بياني بلون الحافة . للقيام بذلك ، يقوم الفرد أيضًا بتوسيع المجموعة إلى ثلاثية ، ولكن أين يتم التعيين من (بدلاً من ) إلى مجموعة الأرقام الطبيعية . من الواضح أن كل حافة يتم إعطاؤها لونًا. من حيث المبدأ ، يكون هذا ممكنًا أيضًا في الرسوم البيانية ذات الحواف المتعددة ، ولكن من الصعب تحديدها ، خاصةً إذا تم تخصيص ألوان متعددة للحواف المختلفة وفقًا لتعددها. ${\displaystyle (V,E)}$${\displaystyle (V,E,f)}$${\displaystyle f}$${\displaystyle E}$${\displaystyle V}$

لاحظ أن المصطلحين "تلوين" و "تلوين" لهما أيضًا معنى أكثر تحديدًا في نظرية الرسم البياني. يتحدث المرء بالضبط عن تلوين صالح ، ولكن عادة ما يتجاهل السمة "صالحة".

وبالمثل ، توجد أيضًا رسوم بيانية مسماة يكون فيها للعقد و / أو الحواف اسم ، وتعين التعيينات أو العقد أو الحواف اسمًا. الأمثلة الموضحة سابقًا تسمى الرسوم البيانية حيث تتم تسمية العقد بالأحرف. غالبًا ما يتم ذلك باستخدام التصورات بحيث يمكن مناقشة الرسم البياني بشكل أفضل. ${\displaystyle (V,E,f,g)}$${\displaystyle f}$${\displaystyle g}$

الرسوم البيانية المرجحة

بدلاً من الرسوم البيانية ذات العقدة أو الحافة ، يتحدث المرء عن الرسوم البيانية ذات العقدة أو الحافة المرجحة إذا تم تعيينها إلى الأرقام الحقيقية بدلاً من التعيين إلى الأرقام الطبيعية . لذلك فإن الرسوم البيانية ذات لون العقدة أو الحافة هي حالات خاصة للرسوم البيانية ذات العقدة أو الحافة المرجحة. ${\displaystyle f}$

نسمي أو نسمي أيضًا وزن العقدة أو الحافة . للتمييز ، يتحدث المرء أيضًا عن وزن العقدة أو وزن الحافة . يصبح هذا الترجيح ضروريًا عندما تكون المعلومات حول علاقات العقد غير كافية. على سبيل المثال ، إذا تم عرض شبكة الطرق (المبسطة) كرسم بياني (الأماكن عبارة عن عقد ، والشوارع التي تربط الأماكن عبارة عن حواف) ، يمكن أن يوفر ترجيح الحواف معلومات حول المسافة بين مكانين. يمكن جمع أوزان حافة الرسم البياني في مصفوفة بوزن مربع ، مصفوفة الجوار .${\displaystyle f(v)}$${\displaystyle f(e)}$${\displaystyle v}$${\displaystyle e}$

التعيينات بين الرسوم البيانية

أخيرًا ، يمكن أيضًا تحديد التعيينات بين الرسوم البيانية. من الأمور ذات الأهمية الخاصة تلك التي تتوافق مع بنية الاثنين ، ما يسمى بـ "تماثل الشكل" .

اسمحوا و أن تكون الرسوم البيانية من نفس النوع. يُطلق على التعيين التشابه بين و إذا: ${\displaystyle G_{1}=\left(V_{1},E_{1}\right)}$${\displaystyle G_{2}=\left(V_{2},E_{2}\right)}$ ${\displaystyle p\colon V_{1}\to V_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$

• في الرسوم البيانية غير الموجهة بدون حواف متعددة :
  إذا كانت حافة ، ثم حافة .${\displaystyle \{v,w\}}$${\displaystyle G_{1}}$${\displaystyle \{p(v),p(w)\}}$${\displaystyle G_{2}}$
• في الرسوم البيانية الموجهة بدون حواف متعددة:
  إذا كانت حافة ، ثم حافة .${\displaystyle (v,w)}$${\displaystyle G_{1}}$${\displaystyle (p(v),p(w))}$${\displaystyle G_{2}}$
• في الرسوم البيانية غير الموجهة ذات الحواف المتعددة : i. ح. أي رأسين متصلين بحد أقصى عدد من الحواف مثل رؤوس صورتهما.
  ${\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}$
• في الرسوم البيانية الموجهة ذات الحواف المتعددة :.
  ${\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}$
• في الرسوم البيانية الموجهة ذات الحواف المتعددة المتميزة: لها شريك مرتبط ولجميع الحواف أيضًا ( وتعتبر بمثابة عوامل تشغيل ، فإن تماثل الشكل البياني هو مجرد تحول طبيعي ).
  ${\displaystyle p}$${\displaystyle q\colon E_{1}\to E_{2}}$${\displaystyle e\in E_{1}}$${\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}$${\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$
• في hypergraphs :
  إذا حافة ، ثم حافة .${\displaystyle \{v_{1},\cdots ,v_{k}\}}$${\displaystyle G_{1}}$${\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}$${\displaystyle G_{2}}$

الصورة p ( G ₁ ) هي إذن رسم بياني فرعي لـ G ₂ . إذا كانت p قابلة للعكس وكانت الوظيفة العكسية أيضًا تماثل الشكل ، فإن p هي تماثل في الرسوم البيانية.

لاحظ أن الرؤوس لها الأسبقية على الحواف بتحديد p كدالة على الرؤوس فقط ، والتي لها تأثير مستحث فقط على الحواف.

التوافقية

يزداد عدد الرسوم البيانية البسيطة غير الموجهة مع العقد بسرعة مع عدد العقد ويساوي . لذلك فهو يزيد أضعافا مضاعفة مع عدد حواف الرسم البياني الكامل . إذا لم يتم ترقيم العقد ، أي أنه لم يتم حساب الرسوم البيانية المتشابهة ، فإن هذا الرقم يتناسب تقريبًا مع معظم فئات التشابه ، حيث تختلف جميع الرسوم البيانية الناتجة عن تبديل العقد المرقمة. يوضح الجدول أدناه استخدام الكمبيوتر${\displaystyle n}$ ${\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}$${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle K_{n}}$${\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}$${\displaystyle n!}$أرقام معينة لـ : ^[6]${\displaystyle n\leq 8}$

هياكل البيانات

رسم بياني غير موجه	مصفوفة الجوار
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$

هناك شكلين أساسيين شائعين لتمثيل الرسوم البيانية في الكمبيوتر : مصفوفة الجوار (أيضًا مصفوفة الحي) وقائمة الجوار (قائمة الجوار). تكمن أهمية التمثيلين في حقيقة أن كل حل خوارزمي عمليًا للمشكلات النظرية للرسم البياني يعود إلى واحد على الأقل من التمثيلين. هناك طريقة أخرى ، ولكنها أقل استخدامًا ، لتمثيل الرسوم البيانية في الكمبيوتر وهي مصفوفة الوقوع ، والتي تُعرف أيضًا باسم مصفوفة حافة العقدة.

في حين أن مصفوفات الوقوع أكثر تكلفة في التنفيذ والصيانة ، فإنها توفر عددًا من المزايا مقارنة بمصفوفات التقارب. من ناحية ، مع وجود عدد ثابت من الحواف ، فإنها دائمًا ما تشغل مقدارًا خطيًا من مساحة التخزين بالنسبة إلى عدد العقد ، وهو أمر مفيد بشكل خاص للرسوم البيانية الرقيقة (أي الرسوم البيانية ذات الحواف القليلة) ، بينما المصفوفة المجاورة يتطلب مساحة مربعة بالنسبة لعدد العقد (ولكنه أكثر إحكاما في الرسوم البيانية الكثيفة ، أي الرسوم البيانية ذات الحواف المتعددة). من ناحية أخرى ، لا يمكن حل العديد من المشكلات النظرية للرسم البياني إلا باستخدام قوائم التقارب في الوقت الخطي . لذلك ، في الممارسة العملية ، عادة ما يتم استخدام هذا الشكل من التمثيل.

برمجة

يوضح المثال التالي في لغة البرمجة C ++ تنفيذ الرسم البياني الموجه مع قوائم التقارب . تم التصريح عن الرسم البياني الموجه كفئة DirectedGraph . يتم استخدام الطريقة الرئيسية عند تنفيذ البرنامج . ^[7]

# تضمين <iostream> 

باستخدام مساحة الاسم المنقولة جنسيا ؛  

// يعلن نوع البيانات لعقد 
عقدة بنية الرسم البياني 
{
    فهرس int _ 
    قيم السلسلة _ 
    عقدة * التالي ؛ 
} ؛

// قم بتعريف نوع البيانات لحواف 
هيكل الرسم  البياني
{
    int startIndex _ 
    int endIndex ؛ 
} ؛


// قم بتعريف فئة فئة  الرسم البياني الموجه DirectedGraph
{
الجمهور :
    عقدة ** headNode ؛ 

    // تُدخل هذه الطريقة عقدة جديدة في قائمة التقارب للرسم البياني وتعيدها كقيمة إرجاع 
Node * insertNode ( فهرس int ، قيمة سلسلة ، عقدة * عقدة )          
    {
        العقدة * newNode = عقدة جديدة ؛ // ينشئ عقدة جديدة من النوع Node newNode -> index = index ؛ // يعين الفهرس newNode -> القيمة = القيمة ؛ // يعين القيمة newNode -> next = node ؛ // يعين مؤشرًا إلى الوريث إرجاع newNode ؛     
           
           
           
         
    }

    // المُنشئ الذي ينشئ الرسم البياني الموجه بالعقد والحواف المعينة 
DirectedGraph ( Node nodes [] ، Edge edges [] ، int numberOfEdges ، int numberOfNodes )           
    {
        headNode = عقدة جديدة * [ numberOfNodes ] () ؛ // يهيئ مصفوفة من المؤشرات للعقد لـ ( int i = 0 ؛ i < numberOfEdges ؛ i ++ ) // للتكرار الحلقي على جميع حواف الرسم البياني {    
                 
        
            int startIndex = الحواف [ i ]. startIndex _ // فهرس عقدة البداية للحافة int endIndex = الحواف [ i ]. إندندكس . // فهرس العقدة النهائية لقيمة سلسلة الحافة = العقد [ endIndex ]. القيم . // قيمة عقدة نهاية عقدة الحافة * newNode = insertNewNode ( endIndex ، value ، headNode [ startIndex ] ) ؛    
                
                
                  // call the insertNewNode method لإدراج عقدة جديدة 
headNode [ startIndex ] = newNode ؛ // يعين المؤشر على العقدة الجديدة }               
        
    }
} ؛

// يطبع جميع العقد المجاورة للعقدة على وحدة التحكم 
باطلة writeAdjacencyList ( Node * node ، int i )    
{
    cout << "العقدة" << ( i + 1 ) << ":" ؛        
    بينما ( عقدة ! = nullptr )   
    {
        cout << "(" << node -> index << "،" << node -> value << ")" ؛          
        عقدة = عقدة -> التالي ؛  
    }
    cout << endl ؛  
}

// الطريقة الرئيسية التي تدير البرنامج 
int main () 
{
    // يصرح ويهيئ المصفوفات للعقد والحواف 
Node nodes [] = { { 0 ، "A" }، { 1 ، "B" }، { 2 ، "C" }، { 3 ، "D" }، { 4 ، "E" } } ؛         
    حواف الحواف [] = { { 0 ، 1 }، { 0 ، 2 }، { 1 ، 4 }، { 2 ، 3 }، { 3 ، 1 }، { 4 ، 3 } } ؛     
    int numberOfNodes = sizeof ( العقد ) / sizeof ( العقد [ 0 ]) ؛ // احصل على عدد العقد int numberOfEdges = sizeof ( edges ) / sizeof ( edges [ 0 ]) ؛ // احصل على عدد الحواف DirectedGraph DirectGraph ( العقد ، الحواف ، numberOfEdges ، numberOfNodes ) ؛ // ينشئ الرسم البياني الموجه بالرؤوس والحواف المحددة      
          
         
    لـ ( int i = 0 ؛ i < numberOfNodes ؛ i ++ ) // لتكرار الحلقة عبر جميع عقد الرسم البياني {         
    
        العقدة * headNode = DirectGraph . headNode [ i ] ؛   
        writeAdjacencyList ( headNode ، i ) ؛ // يطبع قائمة الجوار للعقدة headNode }  
    
}

انظر ايضا

• ألعاب الرسم البياني
• ظاهرة العالم الصغير (شبكة العالم الصغير)
• شبكة خالية من النطاق
• رسم بياني عشوائي
• الرسم البياني الفرقة
• نظام الكمية

المؤلفات

• توماس إتش كورمين ، تشارلز ليسيرسون ، رونالد إل ريفيست ، كليفورد شتاين: الخوارزميات - مقدمة . الطبعة الثانية. Oldenbourg Wissenschaftsverlag ، ميونيخ 2007 ، ISBN 978-3-486-58262-8 ، ص. 531-533 . 
• راينهارد ديستل : نظرية الرسم البياني . الطبعة الرابعة. سبرينغر ، برلين وآخرون. 2010 ، ISBN 978-3-642-14911-5 ( عبر الإنترنت: 4th Electronic Edition 2010 ، إصدار معاينة مجاني - الإصدار الأول: 1996). 
• يورغن إيبرت: خوارزميات الرسم البياني الفعالة . في: نصوص دراسية - علوم حاسب . Akademische Verlags-Gesellschaft ، فيسبادن 1981 ، ISBN 3-400-00424-3 (في نفس الوقت أطروحة التأهيل في جامعة أوسنابروك 1982). 
• ديتر جونجنيكل : الرسوم البيانية والشبكات والخوارزميات . 3rd طبعة منقحة وموسعة بالكامل. BI-Wissenschafts-Verlag ، مانهايم وآخرون 1994 ، ISBN 3-411-14263-4 ( جدول المحتويات [PDF ؛ 1.2 ميغابايت ]). 
• مانفريد نيتشه: رسوم بيانية للمبتدئين. حول منزل سانتا كلوز . في: دراسات . الطبعة الثالثة المنقحة والموسعة. Vieweg + Teubner ، فيسبادن 2009 ، ISBN 978-3-8348-0813-4 . 

التفصيل

1. راينهارد ^ديستل : ^نظرية الرسم البياني . ^{_ _} الطبعة الرابعة. سبرينغر ، برلين وآخرون. 2010 ، ISBN 978-3-642-14911-5 ، ص 1–34 ( على الإنترنت: الطبعة الإلكترونية الرابعة 2010 - الطبعة الأولى: 1996). 
2. الرسوم البيانية الموجهة . في: كلود ساموت ، جيفري آي ويب (محرران): موسوعة التعلم الآلي . سبرينغر الولايات المتحدة ، 2010 ، ص. 279 ، دوى : 10.1007 / 978-0-387-30164-8_218 . 
3. ↑ ^{أ ب} للرسوم البيانية الموجهة: في نفس الاتجاه
4. ↑ [< https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/؟dateline= لا >]
5. ↑ بريجيت ويرنرز: أساسيات بحوث العمليات . الطبعة الثالثة. سبرينغر ، برلين هايدلبرغ 2013 ، ISBN 978-3-642-40101-5 ، ص. 175-209 . 
6. ↑ الحلقة A000088 في OEIS
7. ↑ تعليمات اختبار البرنامج: تنفيذ الرسم البياني في C ++ باستخدام قائمة المجاورة

هذه المقالة متاحة كملف صوتي:

•  |
• حفظ  |
• 26:00 دقيقة  |
• 12.3 ميجابايت  |
• نص النسخة المنطوقة (16 يونيو 2022)

---

مزيد من المعلومات حول ويكيبيديا المنطوقة