مسرد مصطلحات نظرية الرسم البياني

هذا معجم لمصطلحات نظرية الرسوم البيانية . نظرية الرسوم البيانية هي دراسة الرسوم البيانية ، وهي أنظمة من العقد أو الرؤوس المتصلة في أزواج بواسطة خطوط أو حواف..

الرموز

الأقواس المربعة [ ]: $G [S]$ هوالبياني الفرعي المستحث للرسم البياني $G$ لمجموعة الرؤوس الفرعية $S.$
الرمز الأساسي ': يُستخدم الرمز (') غالبًا لتعديل ترميز ثوابت الرسم البياني بحيث ينطبق على الرسم البياني الخطي بدلًا من الرسم البياني المُعطى. على سبيل المثال، $α (G)$ هو عدد الاستقلال للرسم البياني؛ $وα'(G)$ هو عدد التطابق للرسم البياني، وهو يساوي عدد الاستقلال للرسم البياني الخطي الخاص به. وبالمثل، $χ (G)$ هو العدد اللوني للرسم البياني؛ $وχ'(G)$ هو المؤشر اللوني للرسم البياني، وهو يساوي العدد اللوني للرسم البياني الخطي الخاص به.

أ

ممتع: مجموعة جذابة $A$ من رسم بياني موجه $G$ هي مجموعة من الرؤوس بحيث يكون لأي رأس $v\in G\setmined A$ هناك ميزة من $v$ باتجاه رأس $A$ .
لا لوني: العدد اللوني للرسم البياني هو الحد الأقصى لعدد الألوان في عملية التلوين الكاملة. ^{[ 1 ]}
غير دوري: 1. يُقال عن الرسم البياني أنه غير دوري إذا لم يكن يحتوي على دورات. الرسم البياني غير الدوري غير الموجه هو نفسه الغابة . أما الرسم البياني الموجه غير الدوري، وهو رسم بياني موجه بدون دورات موجهة، فيُطلق عليه غالبًا اسم الرسم البياني الموجه غير الدوري ، وخاصة في علوم الحاسوب. ^[²^]; 2. التلوين غير الدوري للرسم البياني غير الموجه هو تلوين مناسب حيث يؤدي كل فئتين لونيتين إلى تكوين غابة. ^[³^]
مصفوفة التجاور: مصفوفة التجاور للرسم البياني هي مصفوفة يتم فيها فهرسة الصفوف والأعمدة برؤوس الرسم البياني، حيث تكون القيمة 1 في الخلية للصف $i$ والعمود $j$ عندما يكون الرأسان $i$ و $j$ متجاورين، و0 فيما عدا ذلك. ^{[ 4 ]}
مجاور: 1. العلاقة بين رأسين يمثلان طرفي نفس الحافة. ^[²^]; 2. العلاقة بين ضلعين مختلفين يشتركان في رأس نهاية واحد. ^[⁵^]
α: بالنسبة للرسم البياني $G$ ، $فإن α (G)$ (باستخدام الحرف اليوناني ألفا) هو رقم استقلاله (انظر مستقل )، و $α'(G)$ هو رقم مطابقته (انظر مطابقة ).
بالتناوب: في الرسم البياني الذي يتضمن تطابقًا، يُعرف المسار المتناوب بأنه مسار تتناوب حوافه بين الحواف المتطابقة وغير المتطابقة. وبالمثل، تُعرف الدورة المتناوبة بأنها دورة تتناوب حوافها بين الحواف المتطابقة وغير المتطابقة. أما المسار المُعزز فهو مسار متناوب يبدأ وينتهي عند رؤوس غير مشبعة. ويمكن إيجاد تطابق أكبر كفرق متناظر بين التطابق والمسار المُعزز؛ ويكون التطابق في أقصى قيمة له إذا وفقط إذا لم يكن له مسار مُعزز.
سلسلة مضادة: في الرسم البياني الموجه غير الدوري ، مجموعة فرعية $S$ من الرؤوس غير القابلة للمقارنة ثنائياً، أي، لأي $x\leq y$ في $المجموعة S$ ، لا يوجد مسار موجه من $x$ إلى $y$ أو من $y$ إلى $x$ . مستوحى من مفهوم السلاسل المضادة في المجموعات المرتبة جزئيًا .
مضاد للحواف: مرادف لكلمة غير حافة ، زوج من الرؤوس غير المتجاورة.
المثلث المضاد: مجموعة مستقلة ذات ثلاثة رؤوس، وهي متممة المثلث.
قمة: 1. الرسم البياني ذو القمة هو رسم بياني يمكن إزالة رأس واحد منه، ليتبقى رسم بياني فرعي مستوٍ . يُسمى الرأس المُزال بالقمة. الرسم البياني $ذو k$ قمة هو رسم بياني يمكن جعله مستويًا بإزالة $k$ رأس.; 2. مرادف للرأس العالمي ، وهو رأس مجاور لجميع الرؤوس الأخرى.
التفرع الشجري: مرادف لشجرة متجذرة وموجهة؛ انظر شجرة .
قوس: انظر إلى الحافة .
سهم: السهم هو زوج مرتب من الرؤوس ، مثل حافة في رسم بياني موجه . يتكون السهم $(س ، ص) من$ ذيل $س$ ، ورأس $ص$ ، واتجاه من $س إلى ص ؛$ ويُقال إن $ص هو$ الخلف المباشر لـ $س،$ و $س هو$ السلف المباشر لـ $ص$ . السهم $(ص ، س)$ هو السهم المعكوس للسهم $(س ، ص)$ .
نقطة التمفصل: رأس في رسم بياني متصل يؤدي حذفه إلى فصل الرسم البياني. وبشكل أعم، رأس يؤدي حذفه إلى زيادة عدد المكونات .
-ary: الشجرة من الرتبة $k$ هي شجرة جذرية لا يزيد عدد أبناء كل رأس داخلي فيها عن $k$ . أما الشجرة من الرتبة 1 فهي مجرد مسار. تُسمى الشجرة من الرتبة 2 أيضًا بالشجرة الثنائية ، مع أن هذا المصطلح يُشير بشكل أدق إلى الأشجار من الرتبة 2 التي يُصنف فيها أبناء كل عقدة إلى أبناء يساريين أو يمينيين (بحد أقصى واحد من كل نوع). تُعتبر الشجرة من الرتبة $k كاملة إذا كان لكل رأس داخلي فيها$ $k$ ابن بالضبط.
زيادة: نوع خاص من المسارات المتناوبة؛ انظر التناوب .
التماثل الذاتي: التماثل الذاتي للرسم البياني هو تناظر للرسم البياني، وهو تماثل من الرسم البياني إلى نفسه.

ب

شنطة: إحدى مجموعات الرؤوس في عملية تفكيك الشجرة .
متوازن: يكون الرسم البياني ثنائي الأجزاء أو متعدد الأجزاء متوازنًا إذا كان حجم كل مجموعتين فرعيتين من تقسيم رؤوسه ضمن نطاق واحد من حجم كل منهما.
كرة: الكرة (وتُعرف أيضًا بكرة الجوار أو كرة المسافة) هي مجموعة جميع الرؤوس التي تبعد مسافة لا تتجاوز r عن رأس معين. بتعبير أدق، بالنسبة لرأس معين v ونصف قطر r، تتكون الكرة B(v,r) من جميع الرؤوس التي يكون أقصر مسار لها إلى v أقل من أو يساوي r.
عرض النطاق الترددي: يُعرَّف عرض نطاق الرسم البياني $G$ بأنه الحد الأدنى، على جميع ترتيبات رؤوس $G$ ، لطول أطول حافة (عدد الخطوات في الترتيب بين طرفيها). وهو أيضًا أقل بواحد من حجم أكبر زمرة في إكمال فاصل زمني مناسب لـ $G$ ، والذي يُختار لتقليل حجم الزمرة.
biclique: مرادف للرسم البياني الثنائي الكامل أو الرسم البياني الفرعي الثنائي الكامل؛ انظر كامل .
ثنائي الاتصال: عادةً ما يُستخدم مصطلح " متصل $برأسين"$ كمرادف لمصطلح "متصل برأسين" ، ولكنه يشمل أحيانًا مصطلح "K2 _" على الرغم من أنه ليس متصلًا برأسين. انظر "متصل" ؛ وللمكونات ثنائية الاتصال ، انظر "مكون" .
رقم الربط: أصغر نسبة ممكنة لعدد جيران مجموعة فرعية مناسبة من الرؤوس إلى حجم المجموعة الفرعية. ^{[ 6 ]}
ثنائي الأجزاء: الرسم البياني ثنائي الأجزاء هو رسم بياني يمكن تقسيم رؤوسه إلى مجموعتين منفصلتين بحيث لا تكون رؤوس إحدى المجموعتين متصلة ببعضها، ولكنها قد تكون متصلة برؤوس المجموعة الأخرى. بعبارة أخرى، الرسم البياني ثنائي الأجزاء هو رسم بياني لا يحتوي على دورات فردية؛ أو بعبارة مكافئة، هو رسم بياني يمكن تلوينه بلونين فقط. غالبًا ما يُكتب الرسم البياني ثنائي الأجزاء $G = (U, V, E)$ حيث $U$ و $V$ هما مجموعتا الرؤوس لكل لون. مع ذلك، ما لم يكن الرسم البياني متصلًا، فقد لا يكون له تلوين ثنائي فريد.
ثنائي الأضلاع: الرسم البياني ثنائي الانتظام هو رسم بياني ثنائي الأجزاء لا يوجد فيه سوى درجتين مختلفتين للرؤوس، واحدة لكل مجموعة من تقسيم الرؤوس الثنائي.
حاجز: 1. كتلة الرسم البياني $G$ هي رسم بياني جزئي أقصى، وهي إما رأس معزول، أو حافة جسرية، أو رسم بياني جزئي متصل ثنائيًا. إذا كانت الكتلة متصلة ثنائيًا، فإن كل زوج من الرؤوس فيها ينتمي إلى دورة مشتركة. كل حافة في الرسم البياني تنتمي إلى كتلة واحدة فقط.; 2. الرسم البياني الكتلي للرسم البياني $G$ هو رسم بياني آخر رؤوسه هي كتل الرسم البياني $G$ ، مع وجود حافة تربط رأسين عندما تشترك الكتل المتناظرة في نقطة مفصلية؛ أي أنه الرسم البياني التقاطعي لكتل الرسم البياني $G.$ الرسم البياني الكتلي لأي رسم بياني هو غابة .; 3. الرسم البياني للقطع الكتلي (أو نقطة القطع الكتلي) للرسم البياني $G$ هو رسم بياني ثنائي الأجزاء، حيث تتكون إحدى مجموعتي الأجزاء من رؤوس القطع في $G$ ، بينما تحتوي الأخرى على رأس $b_{i}$ لكل كتلة $B_{i}$ من $G.$ عندما تكون $G$ متصلة، فإن الرسم البياني لنقاط القطع الكتلية الخاص بها هو شجرة.; 4. الرسم البياني الكتلي (يُسمى أيضًا شجرة الزمر إذا كانت متصلة، ويُطلق عليه أحيانًا خطأً شجرة هوسيمي) هو رسم بياني تكون جميع كتله رسومًا بيانية كاملة. الغابة هي رسم بياني كتلي؛ لذا، على وجه الخصوص، فإن الرسم البياني الكتلي لأي رسم بياني هو رسم بياني كتلي، ويمكن إنشاء كل رسم بياني كتلي كرسم بياني كتلي لرسم بياني آخر.
رابطة: مجموعة القطع الدنيا : مجموعة من الحواف التي يؤدي حذفها إلى فصل الرسم البياني، والتي لا توجد مجموعة فرعية مناسبة لها نفس الخاصية.
كتاب: 1. الكتاب ، أو الرسم البياني للكتاب، أو الكتاب المثلثي هو رسم بياني ثلاثي الأجزاء كامل $K$ $1,1,$ $n$ ؛ مجموعة من $n$ مثلثات متصلة عند حافة مشتركة.; 2. نوع آخر من الرسوم البيانية، ويسمى أيضًا كتابًا، أو كتابًا رباعي الأضلاع، هو مجموعة من $4$ دورات متصلة عند حافة مشتركة؛ وهو حاصل الضرب الديكارتي لنجمة مع حافة.; 3. يُعرَّف تضمين الكتاب بأنه تضمين رسم بياني على كتاب طوبولوجي، وهو فضاء يتكون من ربط مجموعة من أنصاف المستويات على طول خط مشترك. عادةً، يُشترط أن تقع رؤوس التضمين على هذا الخط، الذي يُسمى عمود التضمين الفقري، وأن تقع حواف التضمين ضمن نصف مستوى واحد، أي إحدى صفحات الكتاب.
الحدود: 1. في تضمين الرسم البياني ، يكون مسار الحدود هو الرسم البياني الفرعي الذي يحتوي على جميع الحواف والرؤوس المتصلة بالوجه .
العليق: الشجيرة المتشعبة هي مجموعة من الرسوم البيانية الفرعية المتصلة والمتلامسة، حيث تتلامس رسمتان بيانيتان فرعيتان إذا اشتركتا في رأس واحد أو إذا احتوت كل منهما على نقطة نهاية واحدة لحافة. رتبة الشجيرة المتشعبة هي أصغر حجم لمجموعة رؤوس لها تقاطع غير فارغ مع جميع الرسوم البيانية الفرعية. أما عرض الشجرة للرسم البياني فهو أعلى رتبة لأي من شجيراته المتشعبة.
فرع: مسار من رؤوس من الدرجة الثانية، ينتهي عند رؤوس درجتها لا تساوي اثنين. ^{[ 7 ]}
تحليل الفروع: يُعدّ تفكيك الفروع للرسم البياني G $تجميعًا$ هرميًا لحواف $G$ ، ممثلاً بشجرة ثنائية غير جذرية، حيث تُسمى أوراقها بحواف $G.$ ويُعرّف عرض تفكيك الفروع بأنه الحد الأقصى، على طول الحواف $e$ لهذه الشجرة الثنائية، لعدد الرؤوس المشتركة بين الرسوم البيانية الفرعية المحددة بحواف $G$ في الشجرتين الفرعيتين المفصولتين بـ $e$ . أما عرض فرع $G$ فهو الحد الأدنى لعرض أي تفكيك فروع للرسم البياني $G.$
عرض الفرع: انظر إلى تحليل الفروع .
كوبري: 1. الجسر أو البرزخ أو الحافة المقطوعة هي حافة يؤدي إزالتها إلى فصل الرسم البياني. الرسم البياني الخالي من الجسور هو الرسم البياني الذي لا يحتوي على جسور؛ أو بعبارة أخرى ، الرسم البياني المتصل بحافتين.; ٢. جسر الرسم البياني الفرعي H هو رسم بياني فرعي متصل أقصى، مفصول عن بقية الرسم البياني بواسطة H. أي أنه رسم بياني فرعي أقصى منفصل عن H من حيث الحواف، وينتمي كل رأسين وحواف فيه إلى مسار منفصل داخليًا عن H. قد يكون H مجموعة من الرؤوس . الوتر هو جسر ذو حافة واحدة. في اختبار التسطح ، H عبارة عن دورة، والدورة المحيطية هي دورة تحتوي على جسر واحد على الأكثر؛ ويجب أن تكون حدًا للوجه في أي تمثيل مستوٍ لرسمها البياني.; 3. يمكن أن يُقصد بجسر الدورة مسارًا يربط بين رأسين في الدورة، ولكنه أقصر من أي من المسارين اللذين يربطان بين الرأسين نفسيهما في الدورة. الرسم البياني الموصول بجسر هو رسم بياني يحتوي على جسر في كل دورة من أربعة رؤوس أو أكثر.
بدون جسر: الرسم البياني الخالي من الجسور أو البرزخ هو رسم بياني لا يحتوي على حواف جسرية (أي برزخ)؛ أي أن كل مكون متصل هو رسم بياني متصل بحافتين .
فراشة: 1. يتكون الرسم البياني للفراشة من خمسة رؤوس وستة حواف؛ ويتكون من مثلثين يشتركان في رأس واحد.; 2. شبكة الفراشة هي رسم بياني يستخدم كبنية شبكة في الحوسبة الموزعة، وهي مرتبطة ارتباطًا وثيقًا بالدورات المتصلة بالمكعب .

ج

ج: $C n$ هو رسم بياني دوري $ذو n$ رأس؛ انظر الدورة .
صبار: الرسم البياني للصبار ، أو شجرة الصبار، أو شجرة هوسيمي، هو رسم بياني متصل ينتمي فيه كل ضلع إلى دورة واحدة على الأكثر. وتكون كتل هذا الرسم إما دورات أو أضلاعًا مفردة. وإذا كان كل رأس ينتمي إلى كتلتين على الأكثر، يُسمى حينها صبار عيد الميلاد.
قفص: القفص هو رسم بياني منتظم ذو أصغر رتبة ممكنة لمحيطه.
قانوني
تقديس القديسين: الشكل الكنسي للرسم البياني هو ثابتٌ بحيث يكون للرسمين البيانيين ثوابت متساوية إذا وفقط إذا كانا متماثلين. تُسمى الأشكال الكنسية أيضًا بالثوابت الكنسية أو الثوابت الكاملة، وتُعرَّف أحيانًا فقط للرسوم البيانية ضمن عائلة معينة من الرسوم البيانية. عملية حساب الشكل الكنسي للرسم البياني هي عملية تقنين الرسم البياني.
بطاقة: الرسم البياني المُشكَّل من رسم بياني مُعطى بحذف رأس واحد، وخاصةً في سياق فرضية إعادة البناء . انظر أيضًا: مجموعة أوراق اللعب ، وهي المجموعة المتعددة لجميع أوراق الرسم البياني.
عرض النحت: يُعد عرض النحت مفهومًا لعرض الرسم البياني مشابهًا لعرض الفرع، ولكنه يستخدم التجميعات الهرمية للرؤوس بدلاً من التجميعات الهرمية للحواف.
يرقة: شجرة اليرقة أو اليرقة هي شجرة تُشكل فيها العقد الداخلية مسارًا.
مركز: مركز الرسم البياني هو مجموعة الرؤوس ذات أقل انحراف مركزي .
مركز الثقل: مركز الشجرة هو رأس v $بحيث$ إذا كان متجذرًا عند $v$ ، فلا يوجد رأس آخر له حجم شجرة فرعية أكبر من نصف حجم الشجرة.
سلسلة: 1. مرادف لكلمة " يمشي" .; 2. عند تطبيق أساليب من الطوبولوجيا الجبرية على الرسوم البيانية، عنصر من مجموعة سلسلة معقدة ، أي مجموعة من الرؤوس أو مجموعة من الحواف.
شيجر كونستانت: انظر إلى التوسعة .
الكرز: الكرزة هي مسار على ثلاثة رؤوس. ^{[ 8 ]}
χ: $χ (G)$ (باستخدام الحرف اليوناني χ) هو العدد اللوني لـ G $و$ χ $' (G)$ هو دليل اللون الخاص به؛ انظر اللون والتلوين.
طفل: في الشجرة الجذرية، يكون ابن الرأس $v$ جارًا لـ $v$ على طول حافة خارجية، وهي حافة موجهة بعيدًا عن الجذر.
وتر
وترية: 1. وتر الدورة هو حافة لا تنتمي إلى الدورة، والتي تنتمي كلتا نقطتي نهايتها إلى الدورة.; 2. الرسم البياني الوتر هو رسم بياني يحتوي على وتر في كل دورة من أربعة رؤوس أو أكثر، لذا فإن الدورات المستحثة الوحيدة هي المثلثات.; 3. الرسم البياني الوتر القوي هو رسم بياني وتر يكون فيه كل دورة بطول ستة أو أكثر تحتوي على وتر فردي.; 4. الرسم البياني الثنائي الوتر ليس وترًا (إلا إذا كان غابة)؛ إنه رسم بياني ثنائي الأجزاء حيث تحتوي كل دورة من ستة رؤوس أو أكثر على وتر، لذا فإن الدورات المستحثة الوحيدة هي دورات من 4.; 5. وتر الدائرة هو قطعة مستقيمة تربط نقطتين على الدائرة؛ ويسمى الرسم البياني لتقاطع مجموعة من الأوتار بالرسم البياني للدائرة .
اللوني: يتعلق الأمر بالتلوين؛ انظر اللون . نظرية الرسم البياني اللوني هي نظرية تلوين الرسوم البيانية. العدد اللوني $χ (G)$ هو الحد الأدنى لعدد الألوان اللازمة لتلوين الرسم البياني $G$ بشكل صحيح . $χ'(G)$ هو المؤشر اللوني للرسم البياني G $،$ وهو الحد الأدنى لعدد الألوان اللازمة لتلوين حواف الرسم البياني $G$ بشكل صحيح .
قابل للاختيار
إمكانية الاختيار: يُقال إن الرسم البياني قابل للاختيار من $الدرجة k$ إذا كان يحتوي على قائمة تلوين عندما يكون لكل رأس قائمة من $k$ لونًا متاحًا. وتُعرَّف قابلية اختيار الرسم البياني بأنها أصغر قيمة $لـ k$ تجعله قابلاً للاختيار من $الدرجة k$ .
دائرة: الرسم البياني الدائري هو رسم بياني لتقاطع أوتار الدائرة.
الدائرة: قد تشير الدائرة إلى مسار مغلق أو عنصر من فضاء الدورات (رسم بياني فرعي ممتد من نوع أويلر). رتبة الدائرة للرسم البياني هي بُعد فضاء دوراته.
محيط: محيط الرسم البياني هو طول أطول دورة بسيطة فيه. يكون الرسم البياني هاميلتونيًا إذا وفقط إذا كان محيطه يساوي رتبته .
فصل: 1. فئة الرسوم البيانية أو عائلة الرسوم البيانية هي مجموعة (عادةً ما تكون غير منتهية) من الرسوم البيانية، وغالبًا ما تُعرَّف بأنها الرسوم البيانية التي تمتلك خاصية معينة. يُستخدم مصطلح "فئة" بدلًا من "مجموعة" لأنه، ما لم تُفرض قيود خاصة (مثل تقييد اختيار الرؤوس من مجموعة معينة، وتعريف الحواف بأنها مجموعات من رأسين)، فإن فئات الرسوم البيانية لا تُعتبر عادةً مجموعات عند صياغتها رسميًا باستخدام نظرية المجموعات.; 2. فئة اللون في الرسم البياني الملون هي مجموعة الرؤوس أو الحواف التي لها لون معين.; 3. في سياق نظرية فيزينغ ، المتعلقة بتلوين حواف الرسوم البيانية البسيطة، يُقال إن الرسم البياني من الفئة الأولى إذا كان مؤشره اللوني يساوي درجته القصوى، ومن الفئة الثانية إذا كان مؤشره اللوني يساوي واحدًا زائد الدرجة. ووفقًا لنظرية فيزينغ، فإن جميع الرسوم البيانية البسيطة إما من الفئة الأولى أو من الفئة الثانية.
مخلب: المخلب هو شجرة ذات رأس داخلي واحد وثلاث أوراق، أو ما يعادله الرسم البياني الثنائي الكامل K $1,3 .$ الرسم البياني الخالي من المخالب هو رسم بياني لا يحتوي على رسم بياني فرعي مستحث يمثل مخلباً.
زمرة: الزمرة هي مجموعة من الرؤوس المتجاورة (أو الرسم البياني الجزئي الكامل الناتج عن تلك المجموعة). أحيانًا تُعرَّف الزمرة بأنها مجموعة قصوى من الرؤوس المتجاورة (أو رسم بياني جزئي كامل أقصى)، وهي مجموعة لا تنتمي إلى أي مجموعة (أو رسم بياني جزئي) أكبر منها. الزمرة من الرتبة $k$ هي زمرة من الرتبة $k$ . عدد الزمر $ω (G)$ للرسم البياني $G$ هو رتبة أكبر زمرة فيه. الرسم البياني للزمر في الرسم البياني G هو رسم تقاطع الزمر القصوى في G. انظر أيضًا الزمرة الثنائية ، وهي رسم بياني جزئي ثنائي كامل.
شجرة الزمرة: مرادف لمصطلح الرسم البياني الكتلي .
عرض الزمرة: يُعرَّف عرض الزمرة في الرسم البياني $G$ بأنه الحد الأدنى لعدد التسميات المختلفة اللازمة لإنشاء $G$ من خلال عمليات تُنشئ رأسًا مُصنَّفًا، أو تُشكِّل اتحادًا منفصلًا لرسمين بيانيين مُصنَّفين، أو تُضيف حافة تربط جميع أزواج الرؤوس ذات التسميات المُعطاة، أو تُعيد تسمية جميع الرؤوس ذات التسمية المُعطاة. وتُعرف الرسوم البيانية ذات عرض الزمرة الذي لا يتجاوز $2$ بأنها الرسوم البيانية المُكمِّلة .
مغلق: 1. الجوار المغلق هو الجوار الذي يشمل رأسه المركزي؛ انظر الجوار .; 2. المسار المغلق هو المسار الذي يبدأ وينتهي عند نفس الرأس؛ انظر المسار .; 3. يكون الرسم البياني مغلقًا بشكل متعدٍ إذا كان يساوي إغلاقه المتعدي الخاص به؛ انظر متعدٍ .; 4. تُعتبر خاصية الرسم البياني مغلقة تحت عملية معينة على الرسوم البيانية إذا كان، كلما كانت وسيطة العملية أو وسائطها تمتلك الخاصية، فإن النتيجة تمتلكها أيضًا. على سبيل المثال، الخصائص الوراثية مغلقة تحت الرسوم البيانية الفرعية المستحثة؛ والخصائص الرتيبة مغلقة تحت الرسوم البيانية الفرعية؛ والخصائص المغلقة تحت المحددات الصغرى مغلقة تحت المحددات الصغرى.
إنهاء: 1. للاطلاع على الإغلاق المتعدي للرسم البياني الموجه، انظر إلى المتعدي .; ٢. يُعرَّف إغلاق الرسم البياني الموجه بأنه مجموعة من الرؤوس التي لا توجد لها حواف صادرة إلى رؤوس خارج هذا الإغلاق. على سبيل المثال، يُعدّ المصرف إغلاقًا برأس واحد. وتُعرف مسألة الإغلاق بأنها مسألة إيجاد إغلاق ذي وزن أدنى أو أقصى.
مشترك: يحمل هذا البادئة معاني مختلفة تتعلق عادةً بالرسوم البيانية المكملة . على سبيل المثال، الرسم البياني المكمل هو رسم بياني ينتج عن عمليات تتضمن الإكمال؛ والتلوين المشترك هو تلوين يُنتج فيه كل رأس إما مجموعة مستقلة (كما في التلوين الصحيح) أو زمرة (كما في تلوين المكمل).
لون
تلوين: 1. تلوين الرسم البياني هو تصنيف رؤوس الرسم البياني بواسطة عناصر من مجموعة معينة من الألوان، أو ما يعادل ذلك تقسيم الرؤوس إلى مجموعات فرعية تسمى "فئات الألوان"، كل منها مرتبط بأحد الألوان.; 2. يستخدم بعض المؤلفين مصطلح "التلوين" دون تحديد، للدلالة على التلوين الصحيح، أي التلوين الذي يُخصص ألوانًا مختلفة لنهايات كل حافة. في تلوين الرسوم البيانية، يكمن الهدف في إيجاد تلوين صحيح يستخدم أقل عدد ممكن من الألوان؛ فعلى سبيل المثال، الرسوم البيانية ثنائية الأجزاء هي تلك التي تُلوّن بلونين فقط، وتنص نظرية الألوان الأربعة على أنه يمكن تلوين أي رسم بياني مستوٍ بأربعة ألوان على الأكثر. يُقال إن الرسم البياني مُلوّن بـ $k$ لونًا إذا تم تلوينه (بشكل صحيح) بـ $k$ لونًا، ويُقال إنه قابل للتلوين بـ $k$ لونًا أو مُلوّن بـ $k$ لونًا إذا كان ذلك ممكنًا.; 3. تمت دراسة العديد من أشكال التلوين، بما في ذلك تلوين الحواف (تلوين الحواف بحيث لا تشترك أي حافتين لهما نفس نقطة النهاية في نفس اللون)، وتلوين القوائم (التلوين الصحيح مع تقييد كل رأس بمجموعة فرعية من الألوان المتاحة)، والتلوين غير الدوري (كل رسم بياني فرعي بلونين يكون غير دوري)، والتلوين المشترك (كل فئة لونية تولد مجموعة مستقلة أو زمرة)، والتلوين الكامل (كل فئتين لونيتين تشتركان في حافة)، والتلوين الكلي (يتم تلوين كل من الحواف والرؤوس).; 4. عدد ألوان الرسم البياني يساوي واحدًا زائد درجة انحلاله . سُمّي بذلك لأن تطبيق خوارزمية التلوين الجشعة على ترتيب انحلالي للرسم البياني لا يستخدم أكثر من هذا العدد من الألوان.
رسم بياني للتنقل: الرسم البياني التبادلي لمجموعة أو بشكل عام شبه مجموعة هو رسم بياني غير موجه تكون فيه الرؤوس عناصر من المجموعة / شبه المجموعة ويوجد ضلع بين أي زوج من العناصر التي تتبادل (أي يوجد ضلع بين الرأسين $x$ و $y$ إذا وفقط إذا كان $xy$ $=$ $yx$ ).
قابلية المقارنة: الرسم البياني غير الموجه هو رسم بياني قابل للمقارنة إذا كانت رؤوسه عناصر مجموعة مرتبة جزئيًا ، ويكون رأسان متجاورين عندما يكونان قابلين للمقارنة في الترتيب الجزئي. وبالمثل، فإن الرسم البياني القابل للمقارنة هو رسم بياني ذو اتجاه متعدٍ. ويمكن تعريف العديد من فئات الرسوم البيانية الأخرى على أنها رسوم بيانية قابلة للمقارنة لأنواع خاصة من الترتيب الجزئي.
إطراء: الرسم البياني التكميلي ${\bar {G}}$ الرسم البياني البسيط $G$ هو رسم بياني آخر على نفس مجموعة الرؤوس مثل $G$ ، مع حافة لكل رأسين غير متجاورين في $G.$
مكتمل: 1. الرسم البياني الكامل هو رسم بياني تكون فيه كل رأسين متجاورين: أي أن جميع الحواف الممكنة موجودة. يُرمز للرسم البياني الكامل ذي $n رأسًا غالبًا بالرمز$ $K$ $n$ . الرسم البياني الثنائي الكامل هو رسم بياني تكون فيه كل رأسين على جانبين متقابلين من تقسيم الرؤوس متجاورين. يُرمز للرسم البياني الثنائي الكامل ذي $a$ رأسًا على جانب من التقسيم و $b$ رأسًا على الجانب الآخر غالبًا بالرمز $K$ $a$ $,$ $b$ . وقد تم توسيع المصطلحات والرموز نفسها لتشمل الرسوم البيانية متعددة الأجزاء الكاملة ، وهي الرسوم البيانية التي تُقسم فيها الرؤوس إلى أكثر من مجموعتين فرعيتين، وكل زوج من الرؤوس في مجموعات فرعية مختلفة يكون متجاورًا؛ إذا كان عدد الرؤوس في المجموعات الفرعية هو $a$ $،$ $b$ $،$ $c$ $، ...،$ فإن هذا الرسم البياني يُرمز له بالرمز $K$ $a$ $,$ $b$ $,$ $c$ $, ...$ .; 2. إكمال الرسم البياني المعطى هو رسم بياني فائق يتمتع بخاصية مرغوبة. على سبيل المثال، الإكمال الوتر هو رسم بياني فائق هو رسم بياني وتري.; 3. التطابق الكامل هو مرادف للتطابق المثالي ؛ انظر التطابق .; ٤. التلوين الكامل هو تلوين صحيح يُستخدم فيه كل زوج من الألوان لنهايات ضلع واحد على الأقل. كل تلوين بأقل عدد من الألوان هو تلوين كامل، ولكن قد توجد تلوينات كاملة بأعداد أكبر من الألوان. العدد اللوني للرسم البياني هو الحد الأقصى لعدد الألوان في التلوين الكامل.; 5. الثابت الكامل للرسم البياني هو مرادف للشكل المتعارف عليه، وهو ثابت له قيم مختلفة للرسوم البيانية غير المتماثلة.
عنصر: المكون المتصل في الرسم البياني هو رسم بياني فرعي متصل أقصى. ويُستخدم المصطلح أيضًا للإشارة إلى الرسوم البيانية الفرعية القصوى أو مجموعات فرعية من رؤوس الرسم البياني التي تتمتع بدرجة اتصال أعلى، بما في ذلك المكونات ثنائية الاتصال ، والمكونات ثلاثية الاتصال ، والمكونات المتصلة بقوة .
التكثيف: إن تكثيف الرسم البياني الموجه $G$ هو رسم بياني موجه غير دوري مع رأس واحد لكل مكون متصل بقوة من $G$ ، وحافة تربط أزواج المكونات التي تحتوي على نقطتي النهاية لحافة واحدة على الأقل في $G.$
مخروط: رسم بياني يحتوي على رأس شامل .
يتصل: السبب في الاتصال .
متصل: الرسم البياني المتصل هو الرسم البياني الذي يشكل فيه كل زوج من الرؤوس نهايتي مسار. وتشمل الأشكال الأعلى للاتصال الاتصال القوي في الرسوم البيانية الموجهة (لكل رأسين يوجد مساران من أحدهما إلى الآخر في كلا الاتجاهين)، والرسوم البيانية المتصلة $بـ k$ رأس (إزالة أقل من $k$ رأس لا يمكن أن تفصل الرسم البياني)، والرسوم البيانية المتصلة بـ $k$ حافة (إزالة أقل من $k$ حافة لا يمكن أن تفصل الرسم البياني).
المكون المتصل: مرادف لكلمة مكون .
انقباض: انكماش الحافة هو عملية أساسية تُزيل حافة من الرسم البياني مع دمج الرأسين اللذين كانت تربطهما سابقًا. انكماش الرأس (يُسمى أحيانًا تحديد الرأس) مشابه، لكن الرأسين ليسا بالضرورة متصلين بحافة. يحدث انكماش المسار على مجموعة الحواف في مسار ما، حيث تنكمش لتُشكّل حافة واحدة بين طرفي المسار. عكس انكماش الحافة هو تقسيم الرأس.
كونفرس: الرسم البياني العكسي هو مرادف للرسم البياني المنقول؛ انظر منقول .
جوهر: 1. النواة $k$ هي الرسم البياني الفرعي المستحث الناتج عن إزالة جميع الرؤوس ذات الدرجة الأقل من $k$ ، وجميع الرؤوس التي تصبح درجتها أقل من k $بعد$ عمليات الإزالة السابقة. انظر الانحلال .; 2. النواة هي رسم بياني $G$ بحيث يكون كل تماثل رسم بياني من G $إلى$ نفسه تماثلاً.; 3. جوهر الرسم البياني $G$ هو رسم بياني أدنى $H$ بحيث توجد تشاكلات من G إلى $H$ والعكس $صحيح$ . $H$ فريد حتى التشاكل. يمكن تمثيله كرسم بياني جزئي مستحث من $G$ ، وهو جوهر بمعنى أن جميع تشاكلاته الذاتية هي تشاكلات.; 4. في نظرية مطابقة الرسوم البيانية، فإن جوهر الرسم البياني هو جانب من جوانب تحليل دولماج-مندلسون الخاص به ، والذي يتكون من اتحاد جميع المطابقات القصوى.
كوتري: 1. مكمل الشجرة الممتدة .; 2. بنية شجرة جذرية تستخدم لوصف الرسم البياني المشترك ، حيث يكون كل رأس من رؤوس الرسم البياني المشترك ورقة من أوراق الشجرة، ويتم تسمية كل عقدة داخلية من الشجرة بـ 0 أو 1، ويكون رأسان من رؤوس الرسم البياني المشترك متجاورين إذا وفقط إذا كان سلفهما المشترك الأدنى في الشجرة يحمل الرقم 1.
غطاء: غطاء الرؤوس هو مجموعة الرؤوس المتصلة بكل حافة في الرسم البياني. غطاء الحواف هو مجموعة الحواف المتصلة بكل رأس في الرسم البياني. تغطي مجموعة من الرسوم البيانية الفرعية رسمًا بيانيًا إذا كان اتحادها - رأسًا وحافة - مساويًا للرسم البياني.
شديد الأهمية: الرسم البياني الحرج لخاصية معينة هو رسم بياني يمتلك تلك الخاصية، ولكن كل رسم بياني فرعي ناتج عن حذف رأس واحد لا يمتلكها. على سبيل المثال، الرسم البياني الحرج للعامل هو رسم بياني يمتلك تطابقًا تامًا (عاملًا من الدرجة 1) لكل عملية حذف رأس، ولكنه (لأنه يحتوي على عدد فردي من الرؤوس) لا يمتلك تطابقًا تامًا في حد ذاته. قارن ذلك بالرسم البياني الحرج للعامل ، المستخدم للرسوم البيانية التي لا تمتلك خاصية معينة، ولكن كل عملية حذف رأس واحد منها تمتلكها.
مكعب
مكعب: 1. الرسم البياني المكعب ، وهو الرسم البياني ذو الرؤوس الثمانية لرؤوس وحواف المكعب.; 2. الرسم البياني المكعب الفائق ، وهو تعميم ذو أبعاد أعلى للرسم البياني المكعب.; 3. الرسم البياني المكعب المطوي ، الذي يتكون من مكعب فائق عن طريق إضافة ربط متطابق بين الرؤوس المتقابلة.; 4. الرسم البياني للمكعب المقسم إلى نصفين ، وهو نصف مربع الرسم البياني للمكعب الفائق.; 5. المكعب الجزئي ، وهو رسم بياني فرعي يحافظ على المسافة من مكعب فائق.; 6. مكعب الرسم البياني $G$ هو قوة الرسم البياني $G$ $3$ .; 7. الرسم البياني المكعب ، وهو اسم آخر للرسم البياني المنتظم $من الدرجة 3$ ، والذي يحتوي كل رأس فيه على ثلاثة حواف متصلة.; 8. الدورات المتصلة بالمكعب ، وهو رسم بياني مكعب يتكون من استبدال كل رأس من رؤوس المكعب الفائق بدورة.
يقطع
مجموعة القطع: القطع هو تقسيم رؤوس الرسم البياني إلى مجموعتين فرعيتين، أو مجموعة الحواف التي تمتد عبر هذا التقسيم (وتُعرف أيضًا بمجموعة القطع)، إذا كانت هذه المجموعة غير فارغة. يُقال إن الحافة تمتد عبر التقسيم إذا كانت لها نقاط نهاية في كلتا المجموعتين الفرعيتين. وبالتالي ، فإن إزالة مجموعة القطع من رسم بياني متصل يؤدي إلى فصله.
نقطة القطع: انظر إلى نقطة النطق .
مساحة مقطوعة: فضاء القطع للرسم البياني هو فضاء متجهي GF (2) يحتوي على مجموعة القطع s للرسم البياني كعناصر له والفرق المتناظر للمجموعات كعملية جمع متجهية له.
دورة: 1. قد تكون الدورة نوعًا من أنواع الرسوم البيانية أو نوعًا من أنواع المسارات . كمسار، قد تكون مسارًا مغلقًا (يُسمى أيضًا جولة ) أو ، وهو الأكثر شيوعًا، مسارًا مغلقًا بدون رؤوس متكررة، وبالتالي بدون حواف متكررة (يُسمى أيضًا دورة بسيطة). في الحالة الأخيرة، تُعتبر عادةً رسمًا بيانيًا، أي أن اختيار الرأس الأول والاتجاه يُعتبر عادةً غير مهم؛ أي أن التبديلات الدورية وانعكاسات المسار تُنتج الدورة نفسها. تشمل الأنواع الخاصة المهمة للدورات دورات هاميلتون ، والدورات المستحثة ، والدورات الطرفية ، وأقصر دورة، والتي تُحدد محيط الرسم البياني. الدورة من الرتبة $k$ هي دورة طولها $k$ ؛ على سبيل المثال، الدورة من الرتبة $2$ هي ثنائي الأضلاع ، والدورة من الرتبة $3$ هي مثلث. الرسم البياني للدورة هو رسم بياني هو نفسه دورة بسيطة؛ ويُرمز عادةً للرسم البياني للدورة ذي $n رأسًا بالرمز$ $C$ $n$ .; 2. فضاء الدورة هو فضاء متجهي يتم إنشاؤه بواسطة الدورات البسيطة في الرسم البياني، وغالبًا ما يكون ذلك على حقل مكون من عنصرين ولكن أيضًا على حقول أخرى.

د

DAG: اختصار للرسم البياني الموجه غير الدوري ، وهو رسم بياني موجه بدون أي دورات موجهة.
ظهر السفينة: مجموعة الرسوم البيانية المتعددة المُشكَّلة من رسم بياني واحد $G$ عن طريق حذف رأس واحد بجميع الطرق الممكنة، خاصةً في سياق فرضية إعادة البناء . تُشكَّل مجموعة الحواف بنفس الطريقة عن طريق حذف حافة واحدة بجميع الطرق الممكنة. تُسمى الرسوم البيانية في مجموعة الحواف أيضًا بالبطاقات . انظر أيضًا الرسوم البيانية الحرجة (التي تمتلك خاصية لا تمتلكها أي بطاقة) والرسوم البيانية الهامشي (التي لا تمتلك خاصية تمتلكها جميع البطاقات).
التحلل: انظر إلى تحليل الشجرة ، أو تحليل المسار ، أو تحليل الفرع .
منحط
الانحطاط: الرسم البياني من الرتبة $k$ هو رسم بياني غير موجه، حيث يكون الحد الأدنى لدرجة كل رسم بياني فرعي مُستحث فيه $k$ على الأكثر . وتُعرف درجة انحلال الرسم البياني بأنها أصغر قيمة لـ $k$ تجعله من الرتبة $k$ . أما ترتيب الانحلال فهو ترتيب للرؤوس بحيث يكون لكل رأس الحد الأدنى لدرجة الرسم البياني الفرعي المُستحث له ولجميع الرؤوس اللاحقة؛ ففي ترتيب انحلال الرسم البياني من الرتبة $k$ ، يكون لكل رأس $k$ جار لاحق على الأكثر. ويُعرف الانحلال أيضًا باسم عدد النواة $k$ ، والعرض، والترابط، ويُطلق على مجموع واحد وقيمة الانحلال اسم عدد التلوين أو عدد سيكيريس-ويلف. وقد سُميت الرسوم البيانية من الرتبة $k أيضًا بالرسوم البيانية الاستقرائية$ $k$ .
درجة: 1. درجة رأس في الرسم البياني هي عدد الحواف المتصلة به. ^[²^] درجة الرسم البياني $G$ (أو درجته القصوى) هي أعلى درجات رؤوسه، ويُرمز لها غالبًا بـ $Δ$ $($ $G$ $) ؛$ أما أدنى درجة في $G$ فهي أدنى درجات رؤوسه، ويُرمز لها غالبًا بـ $δ$ $($ $G$ $)$ . تُسمى الدرجة أحيانًا بالتكافؤ ؛ ويمكن الإشارة إلى درجة $v$ في $G$ $بـ$ $dG$ $($ $v$ $)$ أو $d$ $($ $G$ $)$ أو $deg($ $v$ $)$ . الدرجة الكلية هي مجموع درجات جميع الرؤوس؛ وبحسب قاعدة المصافحة، فهي عدد زوجي. تسلسل الدرجات هو مجموعة درجات جميع الرؤوس، مرتبة من الأكبر إلى الأصغر. في الرسم البياني الموجه، يمكن التمييز بين درجة الدخول (عدد الحواف الواردة) ودرجة الخروج (عدد الحواف الصادرة). ^[²^]; 2. درجة التماثل للرسم البياني هي مرادف لعدد هادويجر الخاص به ، وهو رتبة أكبر مجموعة فرعية من الزمر.
Δ ، δ: $Δ (G)$ (باستخدام الحرف اليوناني دلتا) هي الدرجة القصوى لرأس في $G$ ، و $δ (G)$ هي الدرجة الدنيا ؛ انظر الدرجة .
كثافة: في رسم بياني مكون من n عقدة، تُعرَّف الكثافة بأنها نسبة عدد حواف الرسم البياني إلى عدد الحواف في رسم بياني كامل مكون من n عقدة. انظر الرسم البياني الكثيف .
عمق: عمق العقدة في الشجرة الجذرية هو عدد الحواف في المسار من الجذر إلى تلك العقدة. على سبيل المثال، عمق الجذر هو صفر، وعمق أي عقدة مجاورة له هو واحد. وهو مستوى العقدة ناقص واحد. مع ذلك، تجدر الإشارة إلى أن بعض المؤلفين يستخدمون مصطلح " العمق" كمرادف لمستوى العقدة . ^{[ 9 ]}
القطر: قطر الرسم البياني المتصل هو أقصى طول لأقصر مسار . أي أنه أقصى مسافة بين كل زوج من رؤوس الرسم البياني. إذا كان للرسم البياني أوزان على حوافه، فإن قطره الموزون يقيس طول المسار بمجموع أوزان الحواف على طول المسار، بينما يقيس القطر غير الموزون طول المسار بعدد الحواف. أما بالنسبة للرسوم البيانية غير المتصلة، فتختلف التعريفات: فقد يُعرَّف القطر بأنه لانهائي، أو بأنه أكبر قطر لمكون متصل، أو قد يكون غير مُعرَّف.
الماس: الرسم البياني الماسي هو رسم بياني غير موجه بأربعة رؤوس وخمسة حواف.
غير متصل: متصل بقوة . (لا يُخلط بينه وبين غير متصل )
ديجون: الديجون هو دورة بسيطة بطول اثنين في الرسم البياني الموجه أو الرسم البياني المتعدد. لا يمكن أن تظهر الديجونات في الرسوم البيانية البسيطة غير الموجهة لأنها تتطلب تكرار نفس الحافة مرتين، وهو ما يخالف تعريف البساطة .
ثنائي الحروف: مرادف للرسم البياني الموجه . ^{[ 2 ]}
مسار مزدوج: انظر المسار الموجه .
السلف المباشر: ذيل الحافة الموجهة التي يكون رأسها هو الرأس المعطى.
الوريث المباشر: رأس الحافة الموجهة التي يكون ذيلها هو الرأس المعطى.
إخراج: الرسم البياني الموجه هو رسم بياني تكون فيه الحواف ذات اتجاه محدد، من رأس إلى آخر. ^{[ 2 ]} في الرسم البياني المختلط ، تكون الحافة الموجهة أيضًا ذات اتجاه محدد؛ ويمكن تسمية الحواف الموجهة أيضًا بالأقواس أو الأسهم.
القوس الموجه: انظر إلى السهم .
حافة موجهة: انظر إلى السهم .
خط موجه: انظر إلى السهم .
مسار موجه: المسار الذي تكون فيه جميع الحواف متجهة في نفس الاتجاه . إذا كان المسار الموجه يؤدي من الرأس $x$ إلى الرأس $y$ ، فإن $x$ هو الرأس السابق لـ $y$ ، و $y$ هو الرأس اللاحق لـ $x$ ، ويُقال إن $y$ يمكن الوصول إليه من $x$ .
اتجاه: 1. العلاقة غير المتناظرة بين رأسين متجاورين في الرسم البياني ، ممثلة بسهم .; 2. العلاقة غير المتناظرة بين رأسين في مسار موجه .
قطع الاتصال: يؤدي إلى قطع الاتصال .
غير متصل: غير متصل .
غير متصل: 1. يكون الرسمان الفرعيان منفصلين من حيث الحواف إذا لم يشتركا في أي حواف، ومنفصلين من حيث الرؤوس إذا لم يشتركا في أي رؤوس.; 2. الاتحاد المنفصل لاثنين أو أكثر من الرسوم البيانية هو رسم بياني تكون مجموعات رؤوسه وحوافه عبارة عن اتحادات منفصلة للمجموعات المقابلة.
رقم التفكك: تُسمى مجموعة فرعية من الرؤوس في الرسم البياني G بالتفكك إذا كانت تُنتج رسمًا بيانيًا فرعيًا بدرجة قصوى 1.
مسافة: المسافة بين أي رأسين في الرسم البياني هي طول أقصر مسار يكون فيه الرأسان هما نقطتا النهاية.
دوسميل: التقسيم الدوماتي للرسم البياني هو تقسيم الرؤوس إلى مجموعات مهيمنة. ويُعرف العدد الدوماتي للرسم البياني بأنه أكبر عدد من المجموعات المهيمنة في هذا التقسيم.
مسيطر: المجموعة المهيمنة هي مجموعة من الرؤوس تشمل أو تجاور كل رأس في الرسم البياني؛ ويجب عدم الخلط بينها وبين غطاء الرؤوس، وهو مجموعة رؤوس متصلة بجميع حواف الرسم البياني. من الأنواع الخاصة المهمة للمجموعات المهيمنة: المجموعات المهيمنة المستقلة (مجموعات مهيمنة مستقلة في الوقت نفسه) والمجموعات المهيمنة المتصلة (مجموعات مهيمنة تُنشئ رسومًا بيانية فرعية متصلة). تُسمى المجموعة المهيمنة ذات الرأس الواحد أيضًا بالرأس الشامل. عدد الهيمنة للرسم البياني هو عدد الرؤوس في أصغر مجموعة مهيمنة.
مزدوج: الرسم البياني الثنائي للرسم البياني المستوي $G$ هو رسم بياني يحتوي على رأس لكل وجه من أوجه $G.$

هـ

هـ: $E (G)$ هي مجموعة الحواف لـ $G$ ؛ انظر مجموعة الحواف .
أذن: الأذن في الرسم البياني هي مسار قد تتطابق نقاط نهايته ولكن بخلاف ذلك لا توجد فيه تكرارات للرؤوس أو الحواف.
تحلل الأذن: تجزئة الأذن هي تقسيم لحواف الرسم البياني إلى سلسلة من الأذنين، حيث تنتمي كل نقطة نهاية (بعد الأولى) إلى أذن سابقة، ولا تنتمي أي نقطة داخلية إلى أي أذن سابقة. الأذن المفتوحة هي مسار بسيط (أذن بدون رؤوس مكررة)، وتجزئة الأذن المفتوحة هي تجزئة تكون فيها كل أذن بعد الأولى مفتوحة؛ ويكون للرسم البياني تجزئة أذن مفتوحة إذا وفقط إذا كان ثنائي الاتصال. الأذن فردية إذا كان لها عدد فردي من الحواف، وتجزئة الأذن الفردية هي تجزئة تكون فيها كل أذن فردية؛ ويكون للرسم البياني تجزئة أذن فردية إذا وفقط إذا كان حرجًا من حيث العوامل.
الغرابة: الانحراف المركزي للرأس هو أبعد مسافة بينه وبين أي رأس آخر.
حافة: الحافة (إلى جانب الرؤوس) هي إحدى الوحدتين الأساسيتين اللتين تُبنى منهما الرسوم البيانية. لكل حافة رأسان (أو أكثر في الرسوم البيانية الفائقة) تتصل بهما، وتُسمى هذه الرؤوس بنهايتيها. قد تكون الحواف موجهة أو غير موجهة؛ تُسمى الحواف غير الموجهة أيضًا خطوطًا، وتُسمى الحواف الموجهة أيضًا أقواسًا أو أسهمًا. في الرسم البياني البسيط غير الموجه ، يمكن تمثيل الحافة بمجموعة رؤوسها، وفي الرسم البياني البسيط الموجه، يمكن تمثيلها بزوج مرتب من رؤوسها. تُكتب الحافة التي تربط الرأسين $x$ و $y أحيانًا$ $xy$ .
قطع الحواف: مجموعة من الحواف التي يؤدي حذفها إلى فصل الرسم البياني . يُطلق على القطع أحادي الحافة اسم الجسر أو البرزخ أو حافة القطع .
حافة التثبيت: مجموعة حواف الرسم البياني المعطى $G$ ، والتي يرمز إليها أحيانًا بـ $E (G)$ .
رسم بياني بلا حواف: الرسم البياني عديم الحواف أو الرسم البياني المنفصل تمامًا على مجموعة معينة من الرؤوس هو الرسم البياني الذي لا يحتوي على أي حواف. يُطلق عليه أحيانًا اسم الرسم البياني الفارغ، ولكن هذا المصطلح قد يشير أيضًا إلى رسم بياني بدون رؤوس.
التضمين: تمثيل الرسم البياني هو تمثيل طوبولوجي للرسم البياني كمجموعة جزئية من فضاء طوبولوجي، حيث يُمثل كل رأس بنقطة، وكل ضلع بمنحنى تكون نهايتاه نهايتي المنحنى، ولا توجد تقاطعات أخرى بين الرؤوس أو الأضلاع. الرسم البياني المستوي هو رسم بياني له تمثيل من هذا النوع على المستوى الإقليدي، والرسم البياني الحلقي هو رسم بياني له تمثيل من هذا النوع على سطح حلقي. جنس الرسم البياني هو أصغر جنس ممكن لمتشعب ثنائي الأبعاد يمكن تمثيله عليه.
رسم بياني فارغ: 1. رسم بياني بدون حواف على مجموعة غير فارغة من الرؤوس.; 2. الرسم البياني من الرتبة الصفرية ، وهو رسم بياني بدون رؤوس وبدون حواف.
نهاية: نهاية الرسم البياني اللانهائي هي فئة تكافؤ للأشعة، حيث يكون شعاعان متكافئين إذا كان هناك شعاع ثالث يتضمن عددًا لا نهائيًا من الرؤوس من كليهما.
نقطة النهاية: أحد الرأسين المتصلين بحافة معينة، أو أحد الرأسين الأول أو الأخير في مسار أو درب. تُسمى نقطة البداية لحافة موجهة معينة بالذيل، وتُسمى نقطة النهاية الثانية بالرأس .
تعداد: تعداد الرسوم البيانية هو مسألة حصر الرسوم البيانية في فئة معينة منها، كدالة لترتيبها. وبشكل أعم، يمكن أن تشير مسائل التعداد إما إلى مسائل حصر فئة معينة من الكائنات التوافقية (مثل الزمر، والمجموعات المستقلة، والتلوينات، والأشجار الممتدة)، أو إلى مسائل حصر جميع هذه الكائنات خوارزميًا.
أويلر: المسار الأويلري هو مسار يستخدم كل حافة من حواف الرسم البياني مرة واحدة فقط. الدائرة الأويلرية (وتُسمى أيضًا دورة أويلر) هي مسار مغلق يستخدم كل حافة مرة واحدة فقط. الرسم البياني الأويلري هو رسم بياني يحتوي على دائرة أويلر. بالنسبة للرسوم البيانية غير الموجهة، يعني هذا أن الرسم البياني متصل وأن درجة كل رأس زوجية. أما بالنسبة للرسوم البيانية الموجهة، فيعني هذا أن الرسم البياني متصل بقوة وأن درجة الدخول لكل رأس تساوي درجة الخروج. في بعض الحالات، يُخفف شرط الاتصال، ويُطلق على الرسم البياني الذي يستوفي شرط الدرجة فقط اسم الرسم البياني الأويلري.
حتى: قابل للقسمة على اثنين؛ على سبيل المثال، الدورة الزوجية هي دورة طولها زوجي.
موسع: الرسم البياني الموسع هو رسم بياني يكون فيه توسع الحواف أو توسع الرؤوس أو التوسع الطيفي محدودًا بعيدًا عن الصفر.
توسع: 1. إن توسع الحافة، أو العدد متساوي المحيط، أو ثابت شيجر للرسم البياني $G$ هو النسبة الدنيا، على المجموعات الفرعية $S$ التي لا تزيد عن نصف رؤوس $G$ ، لعدد الحواف الخارجة من $S$ إلى عدد الرؤوس في $S.$; 2. إن توسيع الرؤوس، أو عدد الرؤوس المتساوي المحيط، أو تكبير الرسم البياني $G$ هو النسبة الدنيا، على المجموعات الفرعية $S$ التي لا تزيد عن نصف رؤوس $G$ ، لعدد الرؤوس الموجودة خارج $S$ ولكن المجاورة لها إلى عدد الرؤوس في $S.$; 3. إن توسيع الجوار الفريد للرسم البياني $G$ هو النسبة الدنيا، على مجموعات فرعية لا تزيد عن نصف رؤوس $G$ ، لعدد الرؤوس خارج $S$ ولكنها مجاورة لرأس فريد في $S$ إلى عدد الرؤوس في $S.$; 4. التوسع الطيفي للرسم البياني المنتظم $من النوع$ $d$ هو الفجوة الطيفية بين أكبر قيمة ذاتية $d$ لمصفوفة التجاور الخاصة به وثاني أكبر قيمة ذاتية.; 5. تتمتع عائلة من الرسوم البيانية بتوسع محدود إذا كانت جميع قواطعها الضحلة من النوع $r$ لها نسبة من الحواف إلى الرؤوس محدودة بدالة لـ $r$ ، وتوسع متعدد الحدود إذا كانت دالة $r$ متعددة الحدود.

F

وجه: في الرسم البياني المستوي أو تمثيل الرسم البياني ، يُشير مصطلح "الوجه" إلى مُكوّن مُتصل من مجموعة جزئية من المستوى أو سطح التمثيل البياني، ويكون هذا المُكوّن منفصلاً عن الرسم البياني. بالنسبة للتمثيل البياني في المستوى، تكون جميع الأوجه محدودة باستثناء وجه واحد؛ ويُسمى هذا الوجه الاستثنائي الذي يمتد إلى ما لا نهاية بالوجه الخارجي (أو اللانهائي).
عامل: عامل الرسم البياني هو رسم بياني جزئي شامل: أي رسم بياني جزئي يتضمن جميع رؤوس الرسم البياني الأصلي. يُستخدم هذا المصطلح بشكل أساسي في سياق الرسوم البيانية الجزئية المنتظمة: العامل من الرتبة $k$ هو عامل منتظم من الرتبة $k$ . على وجه الخصوص، العامل $من الرتبة 1$ هو نفسه التطابق التام. الرسم البياني الحرج للعامل هو رسم بياني يؤدي حذف أي رأس منه إلى رسم بياني ذي عامل من الرتبة $1$ .
التحليل إلى عوامل: تحليل الرسم البياني هو تقسيم حواف الرسم البياني إلى عوامل؛ والتحليل من الرتبة $k$ هو تقسيم إلى $k$ عوامل. على سبيل المثال، التحليل من الرتبة $1$ هو تلوين للحواف مع خاصية إضافية تتمثل في أن كل رأس متصل بحافة من كل لون.
عائلة: مرادف لكلمة " طبقة" .
محدود: الرسم البياني محدود إذا كان عدد رؤوسه وعدد حوافه محدودين. تفترض العديد من المصادر أن جميع الرسوم البيانية محدودة دون التصريح بذلك صراحةً. الرسم البياني محدود محليًا إذا كان لكل رأس عدد محدود من الحواف المتصلة به. أما الرسم البياني غير المحدود فهو رسم بياني غير محدود: أي أنه يحتوي على عدد لا نهائي من الرؤوس، أو عدد لا نهائي من الحواف، أو كليهما.
الطلب الأول: منطق الرتبة الأولى للرسوم البيانية هو شكل من أشكال المنطق حيث تمثل المتغيرات رؤوس الرسم البياني، ويوجد دالة ثنائية لاختبار ما إذا كان رأسان متجاورين. ويختلف هذا عن منطق الرتبة الثانية، حيث يمكن للمتغيرات أن تمثل مجموعات من الرؤوس أو الحواف.
-رفرف: بالنسبة لمجموعة رؤوس $X$ ، فإن $X$ -flap هو مكون متصل من الرسم البياني الفرعي الناتج عن حذف $X.$ يُستخدم مصطلح "flap" عادةً في سياق " الملاذات" ، وهي دوال تربط مجموعات صغيرة من الرؤوس بـ "flap" الخاصة بها. انظر أيضًا " جسر الدورة"، الذي يكون إما "flap" لرؤوس الدورة أو "وترًا" للدورة.
مُحرَّم: يُعرَّف الرسم البياني المحظور بأنه مجموعة من الرسوم البيانية التي لا تحتوي على رسوم بيانية أخرى كرسوم بيانية فرعية، أو رسوم بيانية فرعية مستحثة، أو رسوم بيانية صغرى. إذا كان الرسم البياني $H$ أحد الرسوم البيانية التي لا تظهر كرسم بياني فرعي، أو رسم بياني فرعي مستحث، أو رسم بياني صغرى، يُقال إن $H$ محظور.
رسم بياني للإجبار: الرسم البياني القسري هو رسم بياني $H$ بحيث يكون تقييم كثافة الرسم البياني الفرعي لـ $H$ في الرسوم البيانية لتسلسل الرسم البياني $G(n)$ كافيًا لاختبار ما إذا كان هذا التسلسل شبه عشوائي .
غابة: الغابة هي رسم بياني غير موجه بدون دورات (اتحاد منفصل لأشجار غير جذرية)، أو رسم بياني موجه يتكون من اتحاد منفصل لأشجار جذرية .
حافة حرة: حافة غير موجودة في تطابق .
رأس حر: 1. رأس لا يقع على حافة متطابقة في عملية مطابقة; 2. رأس لم تتم مطابقته.
فاكهة: 1. روبرت فروشت; 2. مخطط فروشت ، وهو أحد أصغر مخططين مكعبين بدون تناظرات غير تافهة.; 3. نظرية فروشت التي تنص على أن كل مجموعة منتهية هي مجموعة التناظرات لرسم بياني منتهٍ.
ممتلىء: مرادف لكلمة " مستحدث" .
الرسم البياني الوظيفي: الرسم البياني الوظيفي هو رسم بياني موجه حيث يكون لكل رأس درجة خروج تساوي واحدًا. وبصورة مكافئة، فإن الرسم البياني الوظيفي هو غابة زائفة موجهة قصوى.

جي

جي: متغير يُستخدم غالبًا للدلالة على الرسم البياني.
جنس: جنس الرسم البياني هو الحد الأدنى لجنس السطح الذي يمكن تضمينه عليه؛ انظر التضمين .
المسار الجيوديسي: عند استخدامها كاسم، فإن كلمة "جيوديسي" مرادفة لكلمة " أقصر مسار" . وعند استخدامها كصفة، فإنها تعني ما يتعلق بأقصر المسارات أو مسافات أقصر المسارات.
عملاق: في نظرية الرسوم البيانية العشوائية ، يُعرف المكون العملاق بأنه مكون متصل يحتوي على نسبة ثابتة من رؤوس الرسم البياني. في النماذج القياسية للرسوم البيانية العشوائية، يوجد عادةً مكون عملاق واحد على الأكثر.
محيط: محيط الرسم البياني هو طول أقصر دورة فيه .
الرسم البياني: يُعدّ الرسم البيانيّ موضوعًا أساسيًا للدراسة في نظرية الرسوم البيانية، وهو عبارة عن نظام من الرؤوس المتصلة في أزواج بواسطة حواف. غالبًا ما يُقسّم الرسم البيانيّ إلى رسوم بيانية موجّهة أو غير موجّهة، وذلك بحسب ما إذا كانت الحواف ذات اتجاه أم لا. أما الرسوم البيانية المختلطة فتضم كلا النوعين من الحواف.
طماع: يتم إنتاجها بواسطة خوارزمية جشعة . على سبيل المثال، التلوين الجشع للرسم البياني هو تلوين يتم إنتاجه من خلال النظر في الرؤوس بتسلسل معين وتعيين أول لون متاح لكل رأس.
غروتزش: 1. هربرت غروتزش; 2. الرسم البياني غروتزش ، وهو أصغر رسم بياني خالٍ من المثلثات ويتطلب أربعة ألوان في أي تلوين مناسب.; 3. نظرية غروتزش التي تنص على أنه يمكن دائمًا تلوين الرسوم البيانية المستوية الخالية من المثلثات بثلاثة ألوان على الأكثر.
رقم جراندي: 1. عدد غروندي للرسم البياني هو الحد الأقصى لعدد الألوان التي ينتجها التلوين الجشع ، مع ترتيب رؤوس سيئ الاختيار.

ح

ح: متغير يستخدم غالبًا للدلالة على رسم بياني، خاصة عندما يتم بالفعل الإشارة إلى رسم بياني آخر بواسطة $G.$
تلوين H: التلوين $H$ للرسم البياني $G$ (حيث $H$ هو أيضًا رسم بياني) هو تشاكل من $H$ إلى $G.$
خالٍ من الهيدروجين: يُقال عن الرسم البياني أنه خالٍ من $H$ إذا لم يكن له رسم بياني فرعي مستحث متماثل مع $H$ ، أي إذا كان $H$ رسمًا بيانيًا فرعيًا مستحثًا ممنوعًا. الرسوم البيانية الخالية من $H$ هي عائلة جميع الرسوم البيانية (أو غالبًا جميع الرسوم البيانية المنتهية) الخالية من H. $[$ ^{10 ] على} سبيل المثال، الرسوم البيانية الخالية من المثلثات هي الرسوم البيانية التي لا تحتوي على رسم بياني مثلثي كرسم بياني فرعي. خاصية كون الرسم البياني خاليًا $من H$ هي خاصية وراثية دائمًا. يُقال عن الرسم البياني أنه خالٍ من $H$ -minor-free إذا لم يكن له رسم بياني فرعي متماثل مع $H.$
هادويجر: 1. هوغو هادويغر; 2. يُعرف عدد هادويغر للرسم البياني بأنه رتبة أكبر صغرى كاملة للرسم البياني. ويُسمى أيضاً عدد زمرة الانكماش أو درجة التشاكل.; 3. تخمين هادويجر هو التخمين القائل بأن عدد هادويجر لا يقل أبدًا عن العدد اللوني.
الهاميلتوني: المسار الهاميلتوني أو الدورة الهاميلتونية هو مسار شامل بسيط أو دورة شاملة بسيطة: فهو يغطي جميع رؤوس الرسم البياني مرة واحدة فقط. يكون الرسم البياني هاميلتونيًا إذا احتوى على دورة هاميلتونية، وقابلًا للتتبع إذا احتوى على مسار هاميلتوني.
ملاذ: الملاذ $k$ هو دالة تربط كل مجموعة $X$ ذات أقل من $k$ رأس بأحد أطرافها، وغالبًا ما تحقق شروط اتساق إضافية. رتبة الملاذ هي العدد $k$ . يمكن استخدام الملاذات لتوصيف عرض الشجرة للرسوم البيانية المحدودة، ونهايات الرسوم البيانية غير المحدودة وأعداد هادويجر لها.
ارتفاع: 1. ارتفاع العقدة في الشجرة الجذرية هو عدد الحواف في أطول مسار، بعيدًا عن الجذر (أي أن عقدها لها عمق متزايد بشكل صارم)، والذي يبدأ من تلك العقدة وينتهي عند ورقة .; 2. ارتفاع الشجرة الجذرية هو ارتفاع جذرها. أي أن ارتفاع الشجرة هو عدد الحواف في أطول مسار ممكن، ينطلق من الجذر وينتهي عند إحدى الأوراق .; 3. ارتفاع الرسم البياني الموجه غير الدوري هو أقصى طول لمسار موجه في هذا الرسم البياني .
وراثي: الخاصية الوراثية للرسوم البيانية هي خاصية تكون مغلقة تحت الرسوم البيانية الفرعية المستحثة: إذا كان للرسم $البياني G$ خاصية وراثية، فيجب أن يكون لكل رسم بياني فرعي مستحث من $G$ خاصية وراثية أيضًا . قارن بين الخاصية الرتيبة (المغلقة تحت جميع الرسوم البيانية الفرعية) أو الخاصة بالرسوم البيانية الفرعية المغلقة (المغلقة تحت الرسوم البيانية الفرعية).
مسدس: دورة بسيطة تتكون من ستة حواف وستة رؤوس بالضبط.
فتحة: الثقب هو دورة مستحثة طولها أربعة أو أكثر. الثقب الفردي هو ثقب طوله فردي. أما الثقب المضاد فهو رسم بياني فرعي مستحث من الرتبة أربعة، مكمله دورة؛ أو بعبارة أخرى، هو ثقب في الرسم البياني المكمل. يُستخدم هذا المصطلح بشكل أساسي في سياق الرسوم البيانية الكاملة، والتي تتميز، وفقًا لنظرية الرسم البياني الكامل القوي، بأنها الرسوم البيانية الخالية من الثقوب الفردية أو الثقوب المضادة الفردية. الرسوم البيانية الخالية من الثقوب هي نفسها الرسوم البيانية الوترية .
التكافؤ المتماثل: يكون الرسمان البيانيان متكافئين تماثليًا إذا وُجد تماثلان، أحدهما من كل رسم بياني إلى الرسم البياني الآخر.
التماثل: 1. تماثل الرسم البياني هو تطبيق من مجموعة رؤوس رسم بياني إلى مجموعة رؤوس رسم بياني آخر، بحيث يربط الرؤوس المتجاورة برؤوس متجاورة. هذا النوع من التطبيقات بين الرسوم البيانية هو الأكثر شيوعًا في مناهج نظرية الفئات في نظرية الرسوم البيانية. ويمكن وصف تلوين الرسم البياني الصحيح، بشكل مكافئ، بأنه تماثل مع رسم بياني كامل.; 2. درجة التماثل للرسم البياني هي مرادف لعدد هادويجر الخاص به ، وهو رتبة أكبر مجموعة فرعية من الزمر.
قوس كهربائي فائق: حافة فائقة موجهة لها مجموعة مصدر ومجموعة هدف.
هايبر إيدج: الحافة في الرسم البياني الفائق ، التي لها أي عدد من نقاط النهاية، على عكس شرط أن يكون لحواف الرسوم البيانية نقطتا نهاية بالضبط .
مكعب فائق: الرسم البياني للمكعب الفائق هو رسم بياني يتكون من رؤوس وحواف مكعب هندسي فائق .
الرسم البياني الفائق: الرسم البياني الفائق هو تعميم للرسم البياني حيث قد يكون لكل حافة (تسمى الحافة الفائقة في هذا السياق) أكثر من نقطتي نهاية.
نقص: يشير هذا البادئة، بالإضافة إلى خاصية الرسم البياني، إلى رسم بياني لا يمتلك الخاصية المطلوبة، ولكن كل رسم بياني فرعي ناتج عن حذف رأس واحد يمتلكها. على سبيل المثال، الرسم البياني شبه الهاميلتوني هو رسم بياني لا يحتوي على دورة هاميلتونية، ولكن كل حذف رأس واحد منه ينتج رسمًا بيانيًا فرعيًا هاميلتونيًا. قارن بالرسم البياني الحرج ، المستخدم للرسوم البيانية التي تمتلك الخاصية المطلوبة، ولكن كل حذف رأس واحد منها لا يمتلكها. ^{[ 11 ]}

أنا

درجة الدخول: عدد الحواف الواردة في الرسم البياني الموجه؛ انظر الدرجة .
حدوث: العلاقة في الرسم البياني هي زوج من الرأس والحافة بحيث يكون الرأس نقطة نهاية للحافة.
مصفوفة الحدوث: مصفوفة الوقوع للرسم البياني هي مصفوفة يتم فهرسة صفوفها بواسطة رؤوس الرسم البياني، ويتم فهرسة أعمدتها بواسطة الحواف، مع وجود واحد في الخلية للصف $i$ والعمود $j$ عندما يكون الرأس $i$ والحافة $j$ متجاورين، وصفر خلاف ذلك.
حادثة: (صفة) العلاقة بين ضلع وإحدى نقاط نهايته. ^{[ 2 ]}
عدم قابلية المقارنة: الرسم البياني لعدم القابلية للمقارنة هو مكمل الرسم البياني للقابلية للمقارنة ؛ انظر قابلية المقارنة .
مستقل: 1. المجموعة المستقلة هي مجموعة من الرؤوس تُنتج رسمًا بيانيًا فرعيًا بدون حواف. ويمكن تسميتها أيضًا بالمجموعة المستقرة أو الزمرة المشتركة. عدد الاستقلال $α$ $($ $G$ $)$ هو حجم أكبر مجموعة مستقلة .; ٢. في الماترويد الرسومي للرسم البياني، تكون مجموعة فرعية من الحواف مستقلة إذا كان الرسم البياني الفرعي المقابل شجرة أو غابة. في الماترويد ثنائي الدائرة ، تكون مجموعة فرعية من الحواف مستقلة إذا كان الرسم البياني الفرعي المقابل شبه غابة .
اللامبالاة: الرسم البياني للحياد هو اسم آخر للرسم البياني للفترات المناسبة أو الرسم البياني للفترات الوحدوية؛ انظر مناسب .
مستحث: الرسم البياني الفرعي المستحث أو الرسم البياني الفرعي الكامل هو رسم بياني فرعي يتكون من مجموعة فرعية من الرؤوس ومن جميع الحواف التي تقع نهايتاها في تلك المجموعة الفرعية. ومن الحالات الخاصة المسارات المستحثة والدورات المستحثة ، وهي رسوم بيانية فرعية مستحثة تمثل مسارات أو دورات.
حثي: مرادف لكلمة منحط .
لا نهائي: الرسم البياني اللانهائي هو الرسم البياني غير المحدود؛ انظر المحدود .
داخلي: يُعتبر رأس المسار أو الشجرة داخليًا إذا لم يكن ورقة؛ أي إذا كانت درجته أكبر من واحد. ويُقال عن مسارين أنهما منفصلان داخليًا (أو مستقلان ) إذا لم يشتركا في أي رأس، باستثناء الرأس الأول والأخير.
تقاطع: 1. تقاطع رسمين بيانيين هو أكبر رسم بياني فرعي مشترك بينهما، وهو الرسم البياني الذي يتكون من الرؤوس والحواف التي تنتمي إلى كلا الرسمين البيانيين.; 2. الرسم البياني التقاطعي هو رسم بياني تمثل رؤوسه مجموعات أو أشكالًا هندسية، ويتكون ضلع بين رأسين عندما يكون تقاطع المجموعتين أو الشكلين المتناظرين غير فارغ. يمكن تعريف عدة فئات من الرسوم البيانية على أنها رسوم بيانية تقاطعية لأنواع معينة من الأشكال، على سبيل المثال: الرسوم البيانية الوترية (رسوم بيانية تقاطعية لأشجار فرعية من شجرة)، والرسوم البيانية الدائرية (رسوم بيانية تقاطعية لأوتار دائرة)، والرسوم البيانية الفاصلية (رسوم بيانية تقاطعية لفترات خط مستقيم)، والرسوم البيانية الخطية (رسوم بيانية تقاطعية لأضلاع رسم بياني)، والرسوم البيانية الزمرية (رسوم بيانية تقاطعية للزمر القصوى في رسم بياني). كل رسم بياني هو رسم بياني تقاطعي لعائلة معينة من المجموعات، وتُسمى هذه العائلة تمثيلًا تقاطعيًا للرسم البياني. عدد التقاطع للرسم البياني $G$ هو الحد الأدنى لعدد العناصر في أي تمثيل تقاطعي لـ $G.$
فاصلة: 1. الرسم البياني للفترات هو رسم بياني لتقاطع فترات خط مستقيم .; 2. الفترة $[$ $u$ $,$ $v$ $]$ في الرسم البياني هي اتحاد جميع أقصر المسارات من $u$ إلى $v$ .; 3. سمك الفاصل الزمني هو مرادف لعرض المسار .
ثابت: مرادف لكلمة ملكية .
سهم مقلوب: سهم ذو اتجاه معاكس لسهم آخر. السهم ( $ص$ $،$ $س$ $)$ $هو$ السهم المعكوس للسهم $($ $س$ $،$ $ص$ $)$ .
معزول: الرأس المعزول في الرسم البياني هو رأس درجته صفر، أي رأس ليس له حواف متصلة به. ^{[ 2 ]}
متماثل الشكل: يكون الرسمان البيانيان متماثلين إذا كان هناك تماثل بينهما؛ انظر التماثل .
التماثل: التماثل البياني هو تطابق تام يحافظ على التطابق بين رؤوس وحواف رسم بياني ورؤوس وحواف رسم بياني آخر. ويُقال إن الرسمين البيانيين المرتبطين بهذه الطريقة متماثلان.
محيط متساوي: انظر إلى التوسعة .
برزخ: مرادف لكلمة جسر ، بمعنى حافة يؤدي إزالتها إلى فصل الرسم البياني.

ج

ينضم: يتم تكوين وصلة بين رسمين بيانيين من اتحادهما المنفصل بإضافة حافة من كل رأس في أحد الرسمين البيانيين إلى كل رأس في الآخر. وبصورة مكافئة، هي متممة الاتحاد المنفصل للمتممات.

ك

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

ل

ل: $L (G)$ هو الرسم البياني الخطي لـ $G$ ؛ انظر الخط .
ملصق: ١. المعلومات المرتبطة برأس أو حافة في الرسم البياني. الرسم البياني المُصنَّف هو رسم بياني تحمل رؤوسه أو حوافه تسميات. يمكن استخدام مصطلحي "مُصنَّف الرؤوس" أو "مُصنَّف الحواف" لتحديد عناصر الرسم البياني التي تحمل تسميات. يشير تصنيف الرسوم البيانية إلى عدة مسائل مختلفة تتعلق بتعيين تسميات للرسوم البيانية وفقًا لقيود معينة. انظر أيضًا تلوين الرسوم البيانية ، حيث تُفسَّر التسميات على أنها ألوان.; ٢. في سياق تعداد الرسوم البيانية ، تُسمى رؤوس الرسم البياني مُصنفة إذا كانت جميعها قابلة للتمييز عن بعضها البعض. على سبيل المثال، يمكن تحقيق ذلك بتحديد تطابق تام بين الرؤوس والأعداد الصحيحة من ١ إلى رتبة الرسم البياني. عندما تكون الرؤوس مُصنفة، تُحسب الرسوم البيانية المتماثلة (ولكن بترتيبات رؤوس مختلفة) ككائنات منفصلة. في المقابل، عندما تكون الرؤوس غير مُصنفة، لا تُحسب الرسوم البيانية المتماثلة بشكل منفصل.
ورقة: 1. رأس الورقة أو الرأس المتدلي (خاصة في الشجرة) هو رأس درجته $1.$ حافة الورقة أو الحافة المتدلية هي الحافة التي تربط رأس الورقة بجاره الوحيد.; 2. قوة الورقة للشجرة هي رسم بياني تكون رؤوسه هي أوراق الشجرة وتربط حوافه الأوراق التي تكون المسافة بينها في الشجرة على الأكثر عتبة معينة.
طول: في الرسم البياني غير الموزون، يُعرَّف طول الدورة أو المسار أو المشي بعدد الحواف التي يستخدمها. أما في الرسم البياني الموزون، فقد يكون مجموع أوزان الحواف المستخدمة. يُستخدم الطول لتحديد أقصر مسار ، ومحيط (طول أقصر دورة)، وأطول مسار بين رأسين في الرسم البياني.
مستوى: ١. هذا هو عمق العقدة مضافًا إليه واحد، مع أن بعض المراجع ^[^١٢^] تُعرّفه بأنه مرادف للعمق . مستوى العقدة في الشجرة الجذرية هو عدد العقد في المسار من الجذر إلى تلك العقدة. على سبيل المثال، الجذر له المستوى ١، وأي عقدة مجاورة له لها المستوى ٢.; 2. مجموعة من جميع العقد التي لها نفس المستوى أو العمق. ^[¹²^]
خط: مرادف للحافة غير الموجهة. الرسم البياني الخطي $L (G)$ للرسم البياني $G$ هو رسم بياني يحتوي على رأس لكل حافة من $G$ وحافة لكل زوج من الحواف التي تشترك في نقطة نهاية في $G.$
الوصلة: مرادف للانحطاط .
قائمة: 1. قائمة التجاور هي تمثيل حاسوبي للرسوم البيانية لاستخدامها في خوارزميات الرسوم البيانية.; 2. تلوين القائمة هو شكل مختلف من أشكال تلوين الرسم البياني حيث يكون لكل رأس قائمة بالألوان المتاحة.
محلي: الخاصية المحلية للرسم البياني هي خاصية تتحدد فقط من خلال جوارات رؤوس الرسم البياني. على سبيل المثال، يكون الرسم البياني محدودًا محليًا إذا كانت جميع جواراته محدودة.
حلقة: الحلقة أو الحلقة الذاتية هي حافة يكون طرفاها نفس الرأس. وهي تشكل دورة طولها $1. هذه$ الحلقات غير مسموح بها في الرسوم البيانية البسيطة.

م

التكبير: مرادف لتوسيع الرؤوس .
مطابقة: التطابق هو مجموعة من الحواف لا تشترك فيها أي حافتين في أي رأس. يُقال إن الرأس مُطابق أو مُشبع إذا كان أحد طرفي حافة في التطابق. التطابق التام هو تطابق يُطابق كل رأس؛ ويُسمى أيضًا عامل 1، ولا يوجد إلا عندما يكون الترتيب زوجيًا. أما التطابق شبه التام، في رسم بياني ذي ترتيب فردي، فهو تطابق يُشبع جميع الرؤوس باستثناء رأس واحد. التطابق الأقصى هو تطابق يستخدم أكبر عدد ممكن من الحواف؛ ورقم التطابق $α'(G)$ للرسم البياني $G$ هو عدد الحواف في التطابق الأقصى. التطابق الأقصى هو تطابق لا يمكن إضافة أي حواف إليه.
أقصى: 1. يُقال عن رسم بياني جزئي من رسم بياني مُعطى $G$ أنه رسم بياني جزئي أقصى لخاصية معينة إذا كان يمتلك تلك الخاصية، ولم يكن أي رسم بياني فائق آخر له، وهو أيضًا رسم بياني جزئي من $G$ ، يمتلك نفس الخاصية. أي أنه عنصر أقصى من بين الرسوم البيانية الجزئية التي تمتلك تلك الخاصية. على سبيل المثال، الزمرة القصوى هي رسم بياني جزئي كامل لا يمكن توسيعه إلى رسم بياني جزئي كامل أكبر. يجب التمييز بين مصطلح "أقصى" و"أقصى": فالرسم البياني الجزئي الأقصى يكون دائمًا أقصى، ولكن ليس بالضرورة العكس.; 2. يكون الرسم البياني البسيط الذي يتمتع بخاصية معينة هو الرسم البياني الأمثل لتلك الخاصية إذا لم يكن من الممكن إضافة أي حواف أخرى إليه (مع الحفاظ على مجموعة الرؤوس دون تغيير) مع الحفاظ على بساطة الرسم البياني والخاصية نفسها. وبالتالي، على سبيل المثال، الرسم البياني المستوي الأمثل هو رسم بياني مستوٍ بحيث تؤدي إضافة أي حواف أخرى إليه إلى إنشاء رسم بياني غير مستوٍ.
أقصى: يُعتبر الرسم البياني الجزئي لرسم بياني معين $G$ ذا قيمة عظمى لخاصية معينة إذا كان أكبر رسم بياني جزئي (من حيث الترتيب أو الحجم) بين جميع الرسوم البيانية الجزئية التي تتمتع بتلك الخاصية. على سبيل المثال، الزمرة العظمى هي أي من أكبر الزمر في رسم بياني معين.
متوسط: 1. الوسيط لثلاثية من الرؤوس، وهو رأس ينتمي إلى أقصر المسارات بين جميع أزواج الرؤوس، وخاصة في الرسوم البيانية الوسيطة والرسوم البيانية المعيارية .; 2. الرسم البياني الوسيط هو رسم بياني يكون فيه لكل ثلاثة رؤوس وسيط فريد.
مينيل: 1. هنري مينيل، عالم نظرية الرسوم البيانية الفرنسي.; 2. الرسم البياني لـ Meyniel هو رسم بياني يحتوي على كل دورة فردية بطول خمسة أو أكثر تحتوي على وترين على الأقل.
الحد الأدنى: يُعتبر الرسم البياني الجزئي للرسم البياني المعطى أصغر عنصر لخاصية معينة إذا كان يمتلك تلك الخاصية، ولكن لا يوجد رسم بياني جزئي كامل له يمتلك نفس الخاصية. أي أنه عنصر أصغر من بين الرسوم البيانية الجزئية التي تمتلك تلك الخاصية.
الحد الأدنى للقطع: القطع الذي يكون لمجموعة القطع الخاصة به الحد الأدنى من الوزن الإجمالي، وربما يقتصر على القطع التي تفصل زوجًا محددًا من الرؤوس؛ وتتميز بنظرية الحد الأقصى للتدفق والحد الأدنى للقطع .
صغير: يُقال عن الرسم البياني $H أنه رسم بياني$ فرعي لرسم بياني آخر $G$ إذا أمكن الحصول على $H$ بحذف حواف أو رؤوس من $G$ وتقليص حواف في $G.$ ويُقال إنه رسم بياني فرعي سطحي إذا أمكن تشكيله كرسم بياني فرعي بحيث تكون جميع الرسوم البيانية الفرعية من $G$ التي تم تقليصها لتشكيل رؤوس $H$ ذات أقطار صغيرة. ويُقال عن $H أنه رسم بياني$ فرعي طوبولوجي لـ $G$ إذا كان لـ $G$ رسم بياني فرعي يُعد تقسيمًا فرعيًا لـ $H.$ ويُقال عن الرسم البياني أنه خالٍ من الرسوم البيانية الفرعية $H$ إذا لم يكن $H$ رسمًا بيانيًا فرعيًا له. وتُقال عن عائلة من الرسوم البيانية أنها مغلقة تحت الرسوم البيانية الفرعية إذا كانت مغلقة تحت الرسوم البيانية الفرعية؛ وتُحدد نظرية روبرتسون-سيمور أن العائلات المغلقة تحت الرسوم البيانية الفرعية لها مجموعة منتهية من الرسوم البيانية الفرعية المحظورة .
مختلط: الرسم البياني المختلط هو رسم بياني قد يتضمن حوافًا موجهة وغير موجهة.
معياري: 1. الرسم البياني المعياري ، وهو رسم بياني يحتوي فيه كل ثلاثي من الرؤوس على رأس وسيط واحد على الأقل ينتمي إلى أقصر المسارات بين جميع أزواج الثلاثية.; 2. التفكيك المعياري ، وهو تفكيك الرسم البياني إلى رسوم بيانية فرعية تتصل فيها جميع الرؤوس ببقية الرسم البياني بنفس الطريقة.; 3. نمطية تجميع الرسم البياني، الفرق بين عدد الحواف المتقاطعة بين المجموعات وقيمتها المتوقعة.
روتيني: الخاصية الرتيبة للرسوم البيانية هي خاصية مغلقة تحت الرسوم البيانية الفرعية: إذا كان للرسم البياني $G$ خاصية رتيبة، فيجب أن يكون لكل رسم بياني فرعي من $G$ خاصية رتيبة أيضًا . قارن بين الوراثة (المغلقة تحت الرسوم البيانية الفرعية المستحثة) أو الإغلاق الجزئي (المغلق تحت الرسوم البيانية الفرعية).
رسم بياني لمور: الرسم البياني لمور هو رسم بياني منتظم يتحقق فيه حد مور بدقة. حد مور هو متباينة تربط بين درجة الرسم البياني وقطره ورتبته، وقد أثبتها إدوارد ف. مور . كل رسم بياني لمور هو عبارة عن قفص.
متعدد الرسوم البيانية: الرسم البياني المتعدد هو رسم بياني يسمح بوجود علاقات تجاور متعددة (وغالباً ما يسمح بوجود حلقات ذاتية)؛ وهو رسم بياني ليس من الضروري أن يكون بسيطاً.
التجاور المتعدد: التجاور المتعدد أو الحافة المتعددة هو مجموعة من أكثر من حافة تشترك جميعها في نفس نقاط النهاية (في نفس الاتجاه، في حالة الرسوم البيانية الموجهة). يُطلق على الرسم البياني ذي الحواف المتعددة اسم الرسم البياني المتعدد.
التعددية: تعددية الحافة هي عدد الحواف في تجاور متعدد. تعددية الرسم البياني هي أقصى تعددية لأي من حوافه.

شمال

شمال: 1. للاطلاع على رموز الأحياء المفتوحة والمغلقة، انظر إلى الجوار .; 2. غالبًا ما يتم استخدام الحرف $n$ الصغير (خاصة في علوم الكمبيوتر) للدلالة على عدد الرؤوس في رسم بياني معين.
جار
جار: رأس مجاور لرأس معين.
حيّ
حيّ: الجوار المفتوح (أو الجوار) للرأس $v$ هو الرسم البياني الجزئي الناتج عن جميع الرؤوس المجاورة لـ $v$ . يُعرَّف الجوار المغلق بنفس الطريقة، ولكنه يشمل $v$ نفسه أيضًا. يُمكن الإشارة إلى الجوار المفتوح لـ $v$ في الرسم البياني $G بالرمز$ $N G (v)$ أو $N G (v)$ ، وإلى الجوار المغلق بالرمز $N G [v]$ أو $NG [v]$ . عندما لا يُحدد ما إذا كان الجوار مفتوحًا أم مغلقًا، يُفترض أنه مفتوح.
شبكة: رسم بياني يتم فيه ربط السمات (مثل الأسماء) بالعقد و/أو الحواف.
العقدة: مرادف لكلمة "رأس" .
غير حافة: الحافة غير المتجاورة أو الحافة المضادة هي زوج من الرؤوس غير المتجاورة؛ حواف الرسم البياني المكمل.
رسم بياني فارغ: انظر إلى الرسم البياني الفارغ .

يا

غريب: 1. الدورة الفردية هي دورة طولها فردي. محيط الدورة الفردية في الرسم البياني غير الثنائي هو طول أقصر دورة فردية فيه. الثقب الفردي هو حالة خاصة من الدورة الفردية: وهو ثقب مستحث وله أربعة رؤوس أو أكثر.; 2. الرأس الفردي هو رأس درجته فردية. وبحسب نظرية المصافحة، فإن كل رسم بياني غير موجه محدود يحتوي على عدد زوجي من الرؤوس الفردية.; 3. الأذن الفردية هي مسار بسيط أو دورة بسيطة ذات عدد فردي من الحواف، وتستخدم في تحليلات الأذن الفردية للرسوم البيانية الحرجة للعامل؛ انظر الأذن .; 4. الوتر الفردي هو حافة تربط رأسين يفصل بينهما مسافة فردية في دورة زوجية. تُستخدم الأوتار الفردية لتعريف الرسوم البيانية الوترية القوية .; 5. الرسم البياني الفردي هو حالة خاصة من الرسم البياني Kneser ، حيث يحتوي على رأس واحد لكل مجموعة فرعية مكونة من $($ $n$ $-$ $1) عنصرًا من مجموعة مكونة من$ $($ $2n$ $-$ $1)$ عنصرًا، وحافة تربط بين مجموعتين فرعيتين عندما تكون مجموعاتهما المقابلة منفصلة.
يفتح: 1. انظر إلى الحي .; 2. انظر إلى المشي .
طلب: 1. رتبة الرسم البياني $G$ هي عدد رؤوسه، $|$ $V$ $($ $G$ $)|$ . يُستخدم المتغير $n$ غالبًا لهذا العدد. انظر أيضًا الحجم ، أي عدد الحواف.; 2. نوع من منطق الرسوم البيانية ؛ انظر الرتبة الأولى والرتبة الثانية .; 3. ترتيب أو تنظيم الرسم البياني هو ترتيب رؤوسه في تسلسل، خاصة في سياق الترتيب الطوبولوجي (ترتيب الرسم البياني الموجه غير الدوري حيث ينتقل كل ضلع من رأس سابق إلى رأس لاحق في الترتيب) وترتيب الانحلال (ترتيب يكون فيه لكل رأس درجة دنيا في الرسم البياني الفرعي المستحث له وجميع الرؤوس اللاحقة).; 4. للاطلاع على ترتيب الملاذ أو العليق، انظر الملاذ والعليق .
توجيه
موجه: 1. يُعرَّف توجيه الرسم البياني غير الموجه بأنه تعيين اتجاهات لحوافه، مما يحوله إلى رسم بياني موجه. أما الرسم البياني الموجه فهو الرسم البياني الذي تم تعيين توجيه له. فعلى سبيل المثال، الشجرة المتعددة هي شجرة موجهة؛ وهي تختلف عن الشجرة الموجهة (التشعب) في عدم اشتراط اتساق اتجاهات حوافها. ومن أنواع التوجيه الخاصة الأخرى: التوجيهات الدورية ، وهي توجيهات الرسوم البيانية الكاملة؛ والتوجيهات القوية ، وهي توجيهات متصلة بقوة؛ والتوجيهات غير الدورية ، وهي توجيهات غير دورية؛ والتوجيهات الأويلرية ، وهي توجيهات أويلرية؛ والتوجيهات المتعدية ، وهي توجيهات مغلقة بشكل متعدٍ.; 2. الرسم البياني الموجه، يستخدمه بعض المؤلفين كمرادف للرسم البياني الموجه .
درجة خارجية: انظر الدرجة العلمية .
خارجي: انظر إلى الوجه .
المستوى الخارجي: الرسم البياني الخارجي المستوي هو رسم بياني يمكن تضمينه في المستوى (بدون تقاطعات) بحيث تكون جميع الرؤوس على الوجه الخارجي للرسم البياني.

P

أحد الوالدين: في الشجرة الجذرية، يكون أحد والدي الرأس $v$ جارًا لـ $v$ على طول الحافة الواردة، وهي الحافة الموجهة نحو الجذر.
طريق: قد يكون المسار إما مسارًا عاديًا أو مسارًا بدون رؤوس متكررة وبالتالي بدون حواف متكررة (يُسمى أيضًا مسارًا بسيطًا)، وذلك حسب المصدر. ومن الحالات الخاصة المهمة المسارات المستحثة وأقصر المسارات .
تحليل المسار: يُعدّ تجزئة المسار للرسم البياني $G$ تجزئة شجرية، حيث تكون الشجرة الأساسية مسارًا. ويُحدد عرضها بنفس طريقة تجزئة الشجرة، أي أقل بواحد من حجم أكبر مجموعة. ويُعرف الحد الأدنى لعرض أي تجزئة مسار للرسم البياني G $باسم$ عرض المسار للرسم البياني $G.$
عرض المسار: عرض المسار في الرسم البياني $G$ هو الحد الأدنى لعرض تجزئة المسار في $G.$ ويمكن تعريفه أيضًا بدلالة عدد الزمر في إكمال الفترات في $G.$ ويقع دائمًا بين عرض النطاق وعرض الشجرة في $G.$ ويُعرف أيضًا بسماكة الفترة، أو عدد فصل الرؤوس، أو عدد البحث عن العقد.
قلادة: انظر إلى الورقة .
ممتاز: 1. الرسم البياني المثالي هو رسم بياني يكون فيه العدد اللوني مساويًا لعدد الزمر في كل رسم بياني فرعي مُستحث. تُعدّ نظرية الرسم البياني المثالي ونظرية الرسم البياني المثالي القوي نظريتين حول الرسوم البيانية المثالية، حيث تُثبت الأولى أن مُكملاتها مثالية أيضًا، بينما تُثبت الثانية أنها تحديدًا الرسوم البيانية التي لا تحتوي على ثقوب فردية أو ثقوب مضادة.; 2. الرسم البياني القابل للترتيب التام هو رسم بياني يمكن ترتيب رؤوسه بطريقة تُمكّن خوارزمية التلوين الجشعة، باستخدام هذا الترتيب، من تلوين كل رسم بياني فرعي مُستحث على النحو الأمثل. تُعدّ الرسوم البيانية القابلة للترتيب التام فئة فرعية من الرسوم البيانية الكاملة.; 3. التطابق المثالي هو التطابق الذي يشبع كل رأس؛ انظر التطابق .; 4. التحليل المثالي من الدرجة 1 هو تقسيم لحواف الرسم البياني إلى تطابقات مثالية بحيث يشكل كل تطابقين دورة هاميلتونية.
طرفية: 1. الدورة المحيطية أو الدورة غير المنفصلة هي دورة تحتوي على جسر واحد على الأكثر.; 2. الرأس المحيطي هو رأس يكون انحرافه المركزي أقصى ما يمكن. في الشجرة، يجب أن يكون هذا الرأس ورقة.
بيترسن: 1. يوليوس بيترسن (1839-1910)، عالم نظرية الرسوم البيانية الدنماركي.; 2. مخطط بيترسن ، وهو مخطط مكون من 10 رؤوس و15 حافة، ويستخدم بشكل متكرر كمثال مضاد.; 3. نظرية بيترسن التي تنص على أن كل رسم بياني مكعب بدون جسور له تطابق مثالي.
مستوٍ: الرسم البياني المستوي هو رسم بياني له تمثيل على المستوى الإقليدي. الرسم البياني المستوي هو رسم بياني مستوي تم تحديد تمثيله مسبقًا. الرسم البياني المستوي من الرتبة $k$ هو رسم بياني يمكن رسمه في المستوى بحيث لا يتجاوز عدد التقاطعات $k لكل حافة.$
بوليتري: الشجرة المتعددة هي شجرة موجهة؛ أو بعبارة أخرى، رسم بياني موجه غير دوري يكون الرسم البياني الأساسي غير الموجه عبارة عن شجرة.
قوة: 1. قوة الرسم البياني G $k$ $للرسم$ البياني $G$ هي رسم بياني آخر على نفس مجموعة الرؤوس؛ يكون رأسان متجاورين في $G$ $k$ عندما تكون المسافة بينهما في $G على الأكثر$ $k$ . قوة الورقة مفهوم وثيق الصلة، مشتق من قوة الشجرة بأخذ الرسم البياني الفرعي الناتج عن أوراق الشجرة.; 2. تحليل الرسم البياني للقوة هو طريقة لتحليل الشبكات المعقدة من خلال تحديد الزمر، والزمر الثنائية، والنجوم داخل الشبكة.; 3. قوانين القوة في توزيعات الدرجات للشبكات الخالية من المقاييس هي ظاهرة يكون فيها عدد الرؤوس ذات درجة معينة متناسبًا مع قوة الدرجة.
السلف: رأس يسبق رأسًا معينًا في مسار موجه .
برايم: 1. يتم تعريف الرسم البياني الأولي من مجموعة جبرية ، مع رأس لكل عدد أولي يقسم رتبة المجموعة.; 2. في نظرية التفكيك المعياري ، الرسم البياني الأولي هو رسم بياني بدون أي وحدات غير تافهة.; 3. في نظرية الانقسامات ، القطع التي تكون مجموعة قطعها رسمًا بيانيًا ثنائي الأجزاء كاملًا، الرسم البياني الأولي هو رسم بياني بدون أي انقسامات. كل رسم بياني ناتج عن قسمة تفكيك أقصى بواسطة انقسامات هو رسم بياني أولي، أو رسم بياني نجمي، أو رسم بياني كامل.; 4. الرسم البياني الأولي للجداء الديكارتي للرسوم البيانية هو رسم بياني متصل ليس هو نفسه ناتجًا. يمكن تحليل كل رسم بياني متصل بشكل فريد إلى ناتج ديكارتي لرسوم بيانية أولية.
سليم: 1. الرسم البياني الجزئي المناسب هو رسم بياني جزئي يزيل رأسًا واحدًا على الأقل أو حافة واحدة بالنسبة للرسم البياني بأكمله؛ بالنسبة للرسوم البيانية المحدودة، لا تكون الرسوم البيانية الجزئية المناسبة متماثلة أبدًا مع الرسم البياني بأكمله، ولكن بالنسبة للرسوم البيانية اللانهائية يمكن أن تكون كذلك.; 2. التلوين الصحيح هو تعيين ألوان لرؤوس الرسم البياني (التلوين) الذي يعين ألوانًا مختلفة لنقاط نهاية كل حافة؛ انظر اللون .; 3. الرسم البياني للفترات الصحيحة أو الرسم البياني للأقواس الدائرية الصحيحة هو رسم بياني لتقاطع مجموعة من الفترات أو الأقواس الدائرية (على التوالي) بحيث لا تحتوي أي فترة أو قوس على فترة أو قوس آخر. تُسمى الرسوم البيانية للفترات الصحيحة أيضًا بالرسوم البيانية للفترات الوحدوية (لأنها يمكن تمثيلها دائمًا بفترات وحدوية) أو الرسوم البيانية للحياد.
ملكية: خاصية الرسم البياني هي خاصية قد تنطبق على بعض الرسوم البيانية وتختلف عن غيرها، وتعتمد فقط على بنية الرسم البياني دون أي معلومات إضافية كالتسميات. ويمكن وصف خصائص الرسم البياني بشكل مكافئ من خلال فئات الرسوم البيانية (الرسوم البيانية التي تمتلك خاصية معينة). وبشكل أعم، قد تكون خاصية الرسم البياني دالة للرسوم البيانية مستقلة عن المعلومات الإضافية، مثل حجم الرسم البياني أو ترتيبه أو تسلسل درجاته؛ ويُطلق على هذا التعريف الأكثر عمومية للخاصية اسم ثابت الرسم البياني.
غابة زائفة: الغابة الزائفة هي رسم بياني غير موجه يحتوي كل مكون متصل فيه على دورة واحدة على الأكثر، أو رسم بياني موجه يحتوي كل رأس فيه على حافة واحدة خارجة على الأكثر.
رسم بياني زائف: الرسم البياني الزائف هو رسم بياني أو رسم بياني متعدد يسمح بوجود حلقات ذاتية.

سؤال

رسم بياني شبه خطي: الرسم البياني شبه الخطي، أو الرسم البياني ثنائي الأجزاء محليًا، هو رسم بياني يمكن فيه تقسيم الجوار المفتوح لكل رأس إلى مجموعتين. هذه الرسوم البيانية خالية دائمًا من المخالب، وتشمل كحالة خاصة الرسوم البيانية الخطية . تُستخدم هذه الرسوم البيانية في نظرية بنية الرسوم البيانية الخالية من المخالب.
تسلسل الرسم البياني شبه العشوائي: إن سلسلة الرسوم البيانية شبه العشوائية هي سلسلة من الرسوم البيانية التي تشترك في العديد من الخصائص مع سلسلة من الرسوم البيانية العشوائية التي تم إنشاؤها وفقًا لنموذج الرسم البياني العشوائي Erdős–Rényi .
جعبة: الرسم البياني الموجه هو رسم بياني متعدد موجه، كما هو مستخدم في نظرية الفئات . تسمى حواف الرسم البياني الموجه بالأسهم.

R

نصف القطر: نصف قطر الرسم البياني هو الحد الأدنى للانحراف المركزي لأي رأس.
رامانوجان: مخطط رامانوجان هو مخطط يكون توسعه الطيفي أكبر ما يمكن. أي أنه مخطط منتظم من الدرجة $d$ ، بحيث تكون ثاني أكبر قيمة ذاتية لمصفوفة التجاور الخاصة به على الأكثر $2{\sqrt {d-1}}$ .
شعاع: الشعاع، في الرسم البياني اللانهائي، هو مسار بسيط لانهائي له نقطة نهاية واحدة فقط. نهايات الرسم البياني هي فئات تكافؤ الأشعة.
إمكانية الوصول: القدرة على الانتقال من رأس إلى آخر داخل الرسم البياني .
يمكن الوصول إليه: تتمتع بإمكانية وصول إيجابية . يقال إن الرأس $y يمكن الوصول إليه من الرأس$ $x$ إذا كان هناك مسار من $x$ إلى $y$ .
يمكن التعرف عليه: في سياق فرضية إعادة البناء ، تُعتبر خاصية الرسم البياني قابلة للتمييز إذا أمكن تحديد صحتها من خلال مجموعة عناصر الرسم البياني. ومن المعروف أن العديد من خصائص الرسم البياني قابلة للتمييز. إذا كانت فرضية إعادة البناء صحيحة، فإن جميع خصائص الرسم البياني قابلة للتمييز.
إعادة الإعمار: تنص فرضية إعادة البناء على أن كل رسم بياني غير موجه $G$ يتحدد بشكل فريد من خلال مجموعته ، وهي مجموعة متعددة من الرسوم البيانية تتشكل بإزالة رأس واحد من $G$ بجميع الطرق الممكنة. في هذا السياق، تعني إعادة البناء تكوين رسم بياني من مجموعته.
المستطيل: دورة بسيطة تتكون من أربعة حواف وأربعة رؤوس بالضبط.
عادي: يكون الرسم البياني منتظمًا $من الدرجة d$ عندما تكون درجة جميع رؤوسه $d$ . الرسم البياني المنتظم هو رسم بياني يكون منتظمًا من $الدرجة d$ لبعض قيم $d$ .
بطولة منتظمة: البطولة العادية هي بطولة يكون فيها مجموع درجات الدخول مساوياً لمجموع درجات الخروج لجميع الرؤوس.
يعكس: انظر إلى عملية النقل .
جذر: 1. رأس معين في الرسم البياني، وخاصة في الأشجار الموجهة والرسوم البيانية الجذرية .; 2. العملية العكسية لقوة الرسم البياني : الجذر $k$ للرسم البياني $G$ هو رسم بياني آخر على نفس مجموعة الرؤوس بحيث يكون رأسان متجاورين في $G$ إذا وفقط إذا كانت المسافة بينهما لا تتجاوز $k$ في الجذر.

S

مشبع: انظر المطابقة .
رقم البحث: رقم البحث عن العقدة هو مرادف لعرض المسار .
الطلب الثاني: منطق الرتبة الثانية للرسوم البيانية هو شكل من أشكال المنطق حيث يمكن للمتغيرات أن تمثل الرؤوس، والحواف، ومجموعات الرؤوس، وأحيانًا مجموعات الحواف. يتضمن هذا المنطق دوالًا منطقية لاختبار ما إذا كان رأس وحافة متصلين، وكذلك ما إذا كان رأس أو حافة ينتمي إلى مجموعة. ويختلف هذا عن منطق الرتبة الأولى، حيث لا يمكن للمتغيرات أن تمثل سوى الرؤوس.
حلقة ذاتية: مرادف لكلمة حلقة .
رأس الفصل: انظر إلى نقطة النطق .
رقم الفصل: يُعدّ رقم فصل الرؤوس مرادفًا لعرض المسار .
أخ أو أخت: في الشجرة الجذرية، يكون شقيق الرأس $v$ هو الرأس الذي له نفس الرأس الأب مثل $v$ .
رأس تبسيطي: الرأس التبسيطي هو رأس تشكل جواره المغلق زمرة .
بسيط: 1. الرسم البياني البسيط هو رسم بياني خالٍ من الحلقات والروابط المتعددة. أي أن كل ضلع يربط بين نقطتي نهاية مختلفتين، ولا يوجد ضلعان لهما نفس نقطة النهاية. الضلع البسيط هو الضلع الذي لا ينتمي إلى رابطة متعددة. في كثير من الحالات، يُفترض أن الرسوم البيانية بسيطة ما لم يُنص على خلاف ذلك.; 2. المسار البسيط أو الدورة البسيطة هو مسار أو دورة لا تحتوي على رؤوس متكررة وبالتالي لا تحتوي على حواف متكررة.
حوض: في الرسم البياني الموجه، يكون المصرف عبارة عن رأس ليس له حواف صادرة (درجة الخروج تساوي 0).
مقاس: حجم الرسم البياني $G$ هو عدد حوافه، $| E (G)|$ . ^{[ 13 ]} غالبًا ما يُستخدم المتغير $m$ لهذا العدد. انظر أيضًا الترتيب ، وهو عدد الرؤوس.
شبكة العالم الصغير: شبكة العالم الصغير هي رسم بياني لا تكون فيه معظم العقد متجاورة، ولكن يمكن الوصول إلى معظم العقد من أي عقدة أخرى بعدد قليل من القفزات أو الخطوات. وبالتحديد، تُعرَّف شبكة العالم الصغير بأنها رسم بياني تنمو فيه المسافة النموذجية L بين عقدتين مختارتين عشوائيًا (عدد الخطوات المطلوبة) تناسبًا طرديًا مع لوغاريتم عدد العقد N في الشبكة ^{[ 14 ].}
سخرية: الرسم البياني المكعب البسيط والمتصل والخالي من الجسور ذو مؤشر لوني يساوي 4.
مصدر: المصدر، في الرسم البياني الموجه، هو رأس ليس له حواف واردة (درجة الدخول تساوي 0).
فضاء: في نظرية المخططات الجبرية ، يمكن ربط عدة فضاءات متجهة على الحقل الثنائي بمخطط. لكل فضاء متجهات مجموعات من الحواف أو الرؤوس، وفرق متناظر بين المجموعات كعملية جمع متجهات. فضاء الحواف هو فضاء جميع مجموعات الحواف، وفضاء الرؤوس هو فضاء جميع مجموعات الرؤوس. فضاء القطع هو فضاء جزئي من فضاء الحواف، وعناصره هي مجموعات القطع الخاصة بالمخطط. فضاء الدورات هو فضاء جزئي من المخططات الممتدة الأويلرية.
مفتاح البراغي: الموسِّع هو رسم بياني (عادةً ما يكون متفرقًا) تكون فيه أقصر مساراته قريبة من تلك الموجودة في رسم بياني كثيف أو أي فضاء متري آخر. تشمل أنواعه الموسِّعات الهندسية ، وهي رسوم بيانية رؤوسها نقاط في فضاء هندسي؛ والموسِّعات الشجرية ، وهي أشجار ممتدة لرسم بياني تكون مسافاتها قريبة من مسافات الرسم البياني؛ والموسِّعات البيانية، وهي رسوم بيانية فرعية متفرقة لرسم بياني كثيف تكون مسافاتها قريبة من مسافات الرسم البياني الأصلي. أما الموسِّع الجشع فهو موسِّع بياني يُنشأ باستخدام خوارزمية جشعة، وهي خوارزمية تأخذ في الاعتبار جميع الحواف من الأقصر إلى الأطول، وتحتفظ بالحواف اللازمة للحفاظ على تقريب المسافة.
يمتد: يُقال عن الرسم البياني الجزئي أنه شامل عندما يشمل جميع رؤوس الرسم البياني الأصلي. ومن الحالات المهمة الأشجار الشاملة (الرسوم البيانية الجزئية الشاملة التي هي أشجار) والمطابقات التامة (الرسوم البيانية الجزئية الشاملة التي هي مطابقات). ويُطلق على الرسم البياني الجزئي الشامل أيضًا اسم عامل ، خاصةً (ولكن ليس حصراً) عندما يكون منتظمًا.
متناثر: الرسم البياني المتفرق هو الرسم البياني الذي يحتوي على عدد قليل من الحواف مقارنة بعدد رؤوسه. وفي بعض التعريفات، ينبغي أن تنطبق هذه الخاصية نفسها على جميع الرسوم البيانية الفرعية للرسم البياني المعطى.
طيفي
نطاق: طيف الرسم البياني هو مجموعة القيم الذاتية لمصفوفة التجاور الخاصة به. نظرية الرسم البياني الطيفية هي فرع من نظرية الرسم البياني يستخدم الأطياف لتحليل الرسوم البيانية. انظر أيضًا: التوسع الطيفي .
ينقسم: 1. الرسم البياني المنقسم هو رسم بياني يمكن تقسيم رؤوسه إلى زمرة ومجموعة مستقلة. وتُستخدم فئة ذات صلة من الرسوم البيانية، وهي الرسوم البيانية المنقسمة المزدوجة، في برهان نظرية الرسم البياني الكامل القوي.; 2. تقسيم الرسم البياني هو تجزئة رؤوسه إلى مجموعتين جزئيتين غير فارغتين، بحيث تشكل الحواف الممتدة عبر هذا القطع رسمًا بيانيًا جزئيًا ثنائيًا كاملًا. يمكن تمثيل تقسيمات الرسم البياني ببنية شجرية تُسمى تحليل التقسيم . يُسمى التقسيم تقسيمًا قويًا عندما لا يتقاطع مع أي تقسيم آخر. ويُسمى التقسيم غير تافه عندما يحتوي كلا جانبيه على أكثر من رأس واحد. ويُسمى الرسم البياني أوليًا عندما لا يحتوي على أي تقسيمات غير تافهة.; 3. تقسيم الرؤوس (يُسمى أحيانًا فصل الرؤوس) هو عملية بيانية أساسية تقسم رأسًا إلى رأسين، حيث يكون هذان الرأسان الجديدان مجاورين للرؤوس التي كان الرأس الأصلي مجاورًا لها. عكس تقسيم الرؤوس هو انكماش الرؤوس.
مربع: 1. مربع الرسم البياني $G$ هو قوة الرسم البياني $G²$ $؛$ وفي الاتجاه المعاكس، $G$ هو الجذر التربيعي لـ $G²$ $.$ نصف مربع الرسم البياني ثنائي الأجزاء هو الرسم البياني الجزئي لمربعه الناتج عن أحد جانبي التقسيم الثنائي.; 2. الرسم البياني المربع هو رسم بياني مستو يمكن رسمه بحيث تكون جميع الوجوه المحدودة عبارة عن دورات من الدرجة 4 وجميع الرؤوس من الدرجة ≤ 3 تنتمي إلى الوجه الخارجي.; 3. الرسم البياني الشبكي المربع هو رسم بياني شبكي معرف من نقاط في المستوى ذات إحداثيات صحيحة متصلة بحواف طولها وحدة واحدة.
مستقر: المجموعة المستقرة هي مرادف للمجموعة المستقلة .
نجم: النجمة هي شجرة ذات رأس داخلي واحد؛ أو بعبارة أخرى، هي رسم بياني ثنائي الأجزاء كامل $K 1, n$ لبعض $n \geq 2.$ الحالة الخاصة للنجمة ذات الأوراق الثلاث تسمى مخلب.
قوة: قوة الرسم البياني هي النسبة الدنيا لعدد الحواف التي تمت إزالتها من الرسم البياني إلى المكونات التي تم إنشاؤها، على جميع عمليات الإزالة الممكنة؛ وهي مماثلة للصلابة، بناءً على عمليات إزالة الرؤوس.
قوي: 1. للاطلاع على الاتصال القوي والمكونات المتصلة بقوة في الرسوم البيانية الموجهة، انظر الاتصال والمكونات . أما التوجيه القوي فهو توجيه متصل بقوة؛ انظر التوجيه .; 2. للاطلاع على نظرية الرسم البياني المثالي القوي ، انظر إلى كلمة "مثالي" .; 3. الرسم البياني المنتظم بقوة هو رسم بياني منتظم يكون فيه لكل رأسين متجاورين نفس عدد الجيران المشتركين، ولكل رأسين غير متجاورين نفس عدد الجيران المشتركين.; 4. الرسم البياني الوتر القوي هو رسم بياني وتر يكون فيه كل دورة زوجية بطول ستة أو أكثر لها وتر فردي.; 5. الرسم البياني المثالي بقوة هو رسم بياني يحتوي كل رسم بياني فرعي مُستحث فيه على مجموعة مستقلة تُحيط بجميع الزمر القصوى. تُسمى رسوم مينيل البيانية أيضًا "رسوم بيانية مثالية بقوة شديدة" لأن كل رأس فيها ينتمي إلى مثل هذه المجموعة المستقلة.
غابة فرعية: رسم بياني فرعي لغابة .
الرسم البياني الفرعي: الرسم البياني الجزئي للرسم البياني $G$ هو رسم بياني آخر يتكون من مجموعة جزئية من رؤوس وحواف $G.$ يجب أن تتضمن مجموعة الرؤوس جميع نقاط نهاية مجموعة الحواف، ولكن قد تتضمن أيضًا رؤوسًا إضافية. الرسم البياني الجزئي الممتد هو رسم بياني يشمل جميع رؤوس الرسم البياني؛ أما الرسم البياني الجزئي المستحث فهو رسم بياني يشمل جميع الحواف التي تنتمي نقاط نهايتها إلى مجموعة الرؤوس.
الشجرة الفرعية: الشجرة الفرعية هي رسم بياني فرعي متصل من الشجرة. في بعض الأحيان، بالنسبة للأشجار الجذرية، تُعرَّف الأشجار الفرعية على أنها نوع خاص من الرسوم البيانية الفرعية المتصلة، تتكون من جميع الرؤوس والحواف التي يمكن الوصول إليها من رأس مُختار.
خليفة: رأس يأتي بعد رأس معين في مسار موجه .
مُركِّز فائق: المُركِّز الفائق هو رسم بياني يحتوي على مجموعتين فرعيتين متساويتين في الحجم من الرؤوس، $I$ و $O$ ، بحيث أنه لكل مجموعتين فرعيتين متساويتين في الحجم، $S$ من $I$ و $T$ من $O،$ توجد مجموعة من المسارات المنفصلة التي تربط كل رأس في $S$ برأس في $T.$ وتشترط بعض المصادر، بالإضافة إلى ذلك، أن يكون المُركِّز الفائق رسمًا بيانيًا موجهًا غير دوري، حيث $I$ هي مصادره و $O$ هي مصارفه.
الرسم البياني الفائق: الرسم البياني الذي يتكون من إضافة رؤوس أو حواف أو كليهما إلى رسم بياني مُعطى. إذا كان $H$ رسمًا بيانيًا جزئيًا من $G$ ، فإن $G$ هو رسم بياني فائق لـ $H.$

تي

ثيتا: 1. الرسم البياني ثيتا هو اتحاد ثلاثة مسارات منفصلة داخليًا (بسيطة) لها نفس رأسي النهاية المتميزين. ^[¹⁵^]; 2. يتم إنشاء الرسم البياني ثيتا لمجموعة من النقاط في المستوى الإقليدي عن طريق إنشاء نظام من المخاريط المحيطة بكل نقطة وإضافة حافة واحدة لكل مخروط، إلى النقطة التي يكون إسقاطها على شعاع مركزي للمخروط هو الأصغر.; 3. عدد لوفاس أو دالة لوفاس ثيتا للرسم البياني هو ثابت الرسم البياني المرتبط بعدد الزمرة والعدد اللوني الذي يمكن حسابه في وقت متعدد الحدود عن طريق البرمجة شبه المحددة.
رسم بياني لثومسن: مخطط تومسن هو اسم للمخطط الثنائي الكامل $K_{3,3}$ .
الطوبولوجيا: 1. الرسم البياني الطوبولوجي هو تمثيل لرؤوس وحواف الرسم البياني بواسطة نقاط ومنحنيات في المستوى (لا يتجنب بالضرورة التقاطعات).; 2. نظرية الرسم البياني الطوبولوجية هي دراسة تضمينات الرسم البياني.; 3. الفرز الطوبولوجي هو المشكلة الخوارزمية لترتيب رسم بياني موجه غير دوري في ترتيب طوبولوجي، وهو تسلسل رؤوس بحيث ينتقل كل ضلع من رأس سابق إلى رأس لاحق في التسلسل.
منفصل تمامًا: مرادف لكلمة بلا حواف .
رحلة: المسار المغلق هو مسار يبدأ وينتهي عند نفس الرأس ولا يحتوي على حواف متكررة. أما جولات أويلر فهي جولات تستخدم جميع حواف الرسم البياني؛ انظر: أويلر .
بطولة: البطولة هي اتجاه للرسم البياني الكامل؛ أي أنها رسم بياني موجه بحيث يتم توصيل كل رأسين بواسطة حافة موجهة واحدة فقط (تسير في اتجاه واحد فقط من الاتجاهين بين الرأسين).
قابلة للتتبع: الرسم البياني القابل للتتبع هو رسم بياني يحتوي على مسار هاميلتوني.
أثر: نزهة بلا حواف متكررة .
متعدٍ: يتعلق الأمر بخاصية التعدي . الإغلاق المتعدي لرسم بياني موجه معين هو رسم بياني على نفس مجموعة الرؤوس، يحتوي على حافة من رأس إلى آخر، كلما كان للرسم البياني الأصلي مسار يربط بين نفس الرأسين. الاختزال المتعدي لرسم بياني هو رسم بياني أدنى له نفس الإغلاق المتعدي؛ وللرسوم البيانية الموجهة غير الدورية اختزال متعدٍ فريد. التوجيه المتعدي هو توجيه لرسم بياني يمثل إغلاقه المتعدي الخاص؛ وهو موجود فقط في الرسوم البيانية القابلة للمقارنة .
ترجمة: الرسم البياني المنقول لرسم بياني موجه معين هو رسم بياني على نفس الرؤوس، مع عكس اتجاه كل حافة. ويمكن تسميته أيضًا بالعكس أو المعكوس للرسم البياني.
شجرة: 1. الشجرة هي رسم بياني غير موجه متصل وغير دوري، أو رسم بياني موجه يوجد فيه مسار فريد من رأس واحد (جذر الشجرة) إلى جميع الرؤوس المتبقية.; 2. الشجرة من الرتبة $k$ هي رسم بياني يتكون من لصق $($ $k$ $+ 1)$ من الزمر المشتركة على زمر مشتركة من الرتبة $k$ . وبناءً على هذا التعريف، فإن الشجرة بالمعنى المعتاد هي شجرة من الرتبة $1 .$
تحلل الشجرة: يُعرَّف تحليل الشجرة للرسم البياني $G$ بأنه شجرة تُسمى عقدها بمجموعات من رؤوس $G$ ، وتُسمى هذه المجموعات بالحقائب. لكل رأس $v$ ، يجب أن تُنشئ الحقائب التي تحتوي على $v$ شجرة فرعية من الشجرة، ولكل حافة $uv،$ يجب أن توجد حقيبة تحتوي على كل من $u$ و $v$ . عرض تحليل الشجرة هو أقل بواحد من الحد الأقصى لعدد الرؤوس في أي من حقائبه؛ وعرض الشجرة $G$ هو الحد الأدنى لعرض أي تحليل شجرة لـ $G.$
عرض الشجرة: يُعرَّف عرض الشجرة للرسم البياني $G$ بأنه الحد الأدنى لعرض تجزئة الشجرة للرسم البياني $G.$ ويمكن تعريفه أيضًا بدلالة عدد الزمر في الإكمال الوتري للرسم البياني G $،$ أو رتبة الملاذ للرسم البياني G $،$ أو رتبة العليق للرسم البياني $G.$
مثلث: دورة طولها ثلاثة في الرسم البياني. الرسم البياني الخالي من المثلثات هو رسم بياني غير موجه لا يحتوي على أي رسوم بيانية فرعية مثلثة.
تافه: الرسم البياني التافه هو رسم بياني يحتوي على 0 أو 1 رأس. ^{[ 16 ]} يُطلق على الرسم البياني الذي يحتوي على 0 رأس اسم الرسم البياني الصفري .
توران: 1. بال توران; 2. الرسم البياني لتوران هو رسم بياني متعدد الأجزاء كامل ومتوازن.; 3. تنص نظرية توران على أن مخططات توران تحتوي على أكبر عدد من الحواف بين جميع المخططات الخالية من الزمر من رتبة معينة.; 4. تطلب مسألة مصنع الطوب لتوران إيجاد الحد الأدنى لعدد التقاطعات في رسم بياني ثنائي الأجزاء كامل.
التوأم: يكون الرأسان $u و v$ توأمين حقيقيين إذا كان لهما نفس الجوار المغلق : $N G [u] = N G [v]$ (وهذا يعني أن $u$ و $v$ جيران)، ويكونان توأمين زائفين إذا كان لهما نفس الجوار المفتوح : $N G (u) = N G (v))$ (وهذا يعني أن $u$ و $v$ ليسا جيران).

يو

رأس أحادي: في الشجرة الجذرية، الرأس الأحادي هو رأس له رأس ابن واحد فقط.
غير موجه: الرسم البياني غير الموجه هو رسم بياني لا يمكن فيه التمييز بين طرفي كل حافة. انظر أيضًا: الرسم البياني الموجه والمختلط . في الرسم البياني المختلط ، تكون الحافة غير الموجهة أيضًا حافة لا يمكن فيها التمييز بين طرفي الحافة.
زي مُوحد: يكون الرسم البياني الفائق منتظمًا $من الدرجة k$ عندما تحتوي جميع حوافه على $k$ نقطة نهاية، ويكون منتظمًا عندما يكون منتظمًا من الدرجة $k$ لبعض $قيم k$ . على سبيل المثال، الرسوم البيانية العادية هي نفسها الرسوم البيانية الفائقة المنتظمة من الدرجة $2$ .
عالمي: 1. الرسم البياني الشامل هو رسم بياني يحتوي على جميع الرسوم البيانية في عائلة معينة من الرسوم البيانية كرسوم بيانية فرعية، أو جميع الرسوم البيانية ذات حجم أو رتبة معينة ضمن عائلة معينة من الرسوم البيانية.; 2. الرأس الشامل (ويُسمى أيضًا رأس القمة أو الرأس المهيمن) هو رأس مجاور لكل رأس آخر في الرسم البياني. على سبيل المثال، تحتوي الرسوم البيانية الدائرية والرسوم البيانية العتبية المتصلة دائمًا على رأس شامل.; 3. في منطق الرسوم البيانية ، يمكن تسمية الرأس الذي يتم تحديده كمياً بشكل شامل في صيغة ما بالرأس الشامل لتلك الصيغة.
رسم بياني غير مرجح: الرسم البياني الذي لم يتم تعيين أوزان لرؤوسه وحوافه ؛ عكس الرسم البياني الموزون .
رسم بياني للمنفعة: الرسم البياني للمنفعة هو اسم للرسم البياني الثنائي الكامل $K_{3,3}$ .

V

V: انظر مجموعة الرؤوس .
تكافؤ: مرادف لكلمة درجة .
رأس: الرأس (جمعها رؤوس) هو (إلى جانب الحواف) أحد الوحدتين الأساسيتين اللتين تُبنى منهما الرسوم البيانية. غالبًا ما تُعتبر رؤوس الرسوم البيانية كائنات ذرية، بدون بنية داخلية.
قطع رأسي
مجموعة فاصلة: مجموعة من الرؤوس التي يؤدي حذفها إلى فصل الرسم البياني . يُطلق على القطع الذي يحتوي على رأس واحد اسم نقطة التمفصل أو رأس القطع .
مجموعة الرؤوس: مجموعة رؤوس الرسم البياني المعطى $G$ ، والتي يرمز إليها أحيانًا بـ $V (G)$ .
الرؤوس: انظر إلى الرأس .
زيارة ميدانية: 1. فاديم ج. فيزينغ; 2. نظرية فيزينغ التي تنص على أن الدليل اللوني يزيد بمقدار واحد على الأكثر عن الدرجة القصوى.; 3. تخمين فيزينغ حول عدد الهيمنة للمنتجات الديكارتية للرسوم البيانية.
مقدار: مجموع درجات مجموعة من الرؤوس.

دبليو

$دبليو$: يُستخدم الحرف $W في تدوين$ الرسوم البيانية للعجلات ورسوم طواحين الهواء . هذا التدوين غير موحد.
فاغنر: 1. كلاوس فاغنر; 2. مخطط فاغنر ، وهو سلم موبيوس ذو ثمانية رؤوس.; 3. نظرية فاغنر التي تميز الرسوم البيانية المستوية بواسطة صغارها المحظورة.; 4. نظرية فاغنر التي تميز الرسوم البيانية الخالية من $K$ $5 -minor.$
يمشي: المسار هو سلسلة منتهية أو غير منتهية من الحواف التي تربط سلسلة من الرؤوس . تُسمى المسارات أحيانًا بالسلاسل . ^[¹⁷^] يكون المسار مفتوحًا إذا كان رأساه الأول والأخير مختلفين، ومغلقًا إذا تكررا.
اتصال ضعيف: يُطلق على الرسم البياني الموجه اسم الرسم البياني المتصل بشكل ضعيف إذا أدى استبدال جميع حوافه الموجهة بحواف غير موجهة إلى إنتاج رسم بياني متصل (غير موجه).
وزن: قيمة عددية تُخصص كعلامة لرأس أو حافة في الرسم البياني. وزن الرسم البياني الفرعي هو مجموع أوزان الرؤوس أو الحواف الموجودة داخله.
الرسم البياني الموزون: الرسم البياني الذي تم تعيين أوزان s لرؤوسه أو حوافه . الرسم البياني الموزون بالرؤوس له أوزان على رؤوسه، والرسم البياني الموزون بالحواف له أوزان على حوافه.
ألوان جيدة: الرسم البياني الملون بشكل جيد هو الرسم البياني الذي تستخدم جميع ألوانه الجشعة نفس عدد الألوان.
تغطية جيدة: الرسم البياني المغطى جيداً هو الرسم البياني الذي تكون جميع مجموعاته المستقلة القصوى متساوية في الحجم.
عجلة: الرسم البياني الدائري هو رسم بياني يتكون من إضافة رأس عام إلى دورة بسيطة.
عرض: 1. مرادف للانحطاط .; 2. للاطلاع على ثوابت الرسم البياني الأخرى المعروفة باسم العرض، انظر bandwidth و branchwidth و clique-width و pathwidth و treewidth .; 3. عرض تجزئة الشجرة أو تجزئة المسار هو أقل بواحد من الحجم الأقصى لإحدى حقائبها، ويمكن استخدامه لتحديد عرض الشجرة وعرض المسار.; 4. عرض الرسم البياني الموجه غير الدوري هو الحد الأقصى لعدد عناصر السلسلة المضادة.
طاحونة هوائية: الرسم البياني لطاحونة الهواء هو اتحاد مجموعة من الزمر، وكلها من نفس الرتبة، مع رأس مشترك واحد ينتمي إلى جميع الزمر وجميع الرؤوس والحواف الأخرى متميزة.

انظر أيضاً

مراجع

↑ فاربر، م.؛ هان، ج.؛ هيل، ب .؛ ميلر، د. ج. (1986)، "حول العدد اللوني للرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 40 (1): 21-39 ، doi : 10.1016/0095-8956(86)90062-6.
1 2 3 4 5 6 7 8 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد ( 2001)، "ب.4 الرسوم البيانية"، مقدمة في الخوارزميات ( الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، الصفحات 1080-1084 .
↑ غرونباوم، ب. (1973)، "التلوينات غير الدورية للرسوم البيانية المستوية"، مجلة إسرائيل للرياضيات ، 14 (4): 390-408 ، doi : 10.1007/BF02764716.
^ كورمين وآخرون. (2001) ، ص. 529.
↑ ديستل، راينهارد (2017)، "1.1 الرسوم البيانية"، نظرية الرسوم البيانية ، نصوص الدراسات العليا في الرياضيات، المجلد 173 ( الطبعة الخامسة)، برلين، نيويورك: سبرينغر-فيرلاغ، ص 3، doi : 10.1007/978-3-662-53622-3 ، ISBN 978-3-662-53621-6.
↑ وودال، د. ر. (1973)، "رقم الربط للرسم البياني ورقم أندرسون الخاص به"، مجلة نظرية التوافيق، السلسلة ب ، 15 (3): 225-255 ، doi : 10.1016/0095-8956(73)90038-5
↑ فان دير هولست، هاين (مارس 2009)، "خوارزمية زمنية متعددة الحدود لإيجاد تضمين بدون روابط للرسم البياني" ، مجلة نظرية التوافيق، السلسلة ب ، 99 (2)، إلسيفير بي في: 512-530 ، doi : 10.1016/j.jctb.2008.10.002
↑ سوداكوف، بيني؛ فوليك، جان (2017)، "نسخ ملونة بشكل صحيح ونسخ قوس قزح من الرسوم البيانية مع عدد قليل من الكرز"، مجلة نظرية التوافيق، السلسلة ب ، 122 (1): 391-416 ، arXiv : 1504.06176 ، doi : 10.1016/j.jctb.2016.07.001.
↑ العمق ، المعهد الوطني للمعايير والتكنولوجيا
↑ براندشتات، أندرياس ؛ لي، فان بانغ؛ سبينراد، جيريمي (1999)، "الفصل 7: الرسم البياني الفرعي المحظور"، فئات الرسوم البيانية: دراسة استقصائية ، سلسلة دراسات SIAM في الرياضيات المتقطعة وتطبيقاتها، الصفحات 105-121 ، ISBN 978-0-89871-432-6
↑ ميتشيم، جون (1969)، "الخصائص الفرعية في الرسوم البيانية"، الجوانب المتعددة لنظرية الرسوم البيانية (وقائع المؤتمر، جامعة غرب ميشيغان، كالامازو، ميشيغان، 1968) ، سلسلة محاضرات في الرياضيات، المجلد 110، سبرينغر، الصفحات 223-230 ، doi : 10.1007/BFb0060121 ، ISBN 978-3-540-04629-5، MR 0253932 .
المستوى 1 2 ، المعهد الوطني للمعايير والتكنولوجيا
↑ هاريس، جون م. (2000)، التوافقية ونظرية الرسم البياني ، نيويورك: سبرينغر-فيرلاغ، ص 5، ISBN 978-0-387-98736-1
↑ واتس، دنكان جيه؛ ستروغاتز، ستيفن إتش (يونيو 1998)، "الديناميكيات الجماعية لشبكات 'العالم الصغير'"، مجلة نيتشر ، 393 (6684): 440-442 ، رمز Bibcode : 1998Natur.393..440W ، doi : 10.1038/30918 ، PMID 9623998 ، S2CID 4429113
↑ بوندي، جيه إيه (1972)، "نظرية الرسم البياني للأبجدية اليونانية"، نظرية الرسم البياني وتطبيقاتها (وقائع المؤتمر، جامعة ويسترن ميشيغان، كالامازو، ميشيغان، 1972؛ مُهدى إلى ذكرى جيه دبليو تي يونغز) ، سلسلة محاضرات في الرياضيات، المجلد 303، سبرينغر، الصفحات 43-54 ، doi : 10.1007/BFb0067356 ، ISBN 978-3-540-06096-3، MR 0335362
↑ ديستل، راينهارد (2017)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 2، doi : 10.1007/978-3-662-53622-3 ، ISBN 978-3-662-53621-6
↑ "نظرية الرسم البياني المتسلسل" ، britannica.com ، تم الاطلاع عليه بتاريخ 25 مارس 2018

[1] فاربر، م.؛ هان، ج.؛ هيل، ب .؛ ميلر، د. ج. (1986)، "حول العدد اللوني للرسوم البيانية"، مجلة نظرية التوافيق، السلسلة ب ، 40 (1): 21-39 ، doi : 10.1016/0095-8956(86)90062-6.

[clrs-2] 1 2 3 4 5 6 7 8 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد ( 2001)، "ب.4 الرسوم البيانية"، مقدمة في الخوارزميات ( الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، الصفحات 1080-1084 .

[3] غرونباوم، ب. (1973)، "التلوينات غير الدورية للرسوم البيانية المستوية"، مجلة إسرائيل للرياضيات ، 14 (4): 390-408 ، doi : 10.1007/BF02764716.

[4] كورمين وآخرون. (2001) ، ص. 529.

[diestel-5] ديستل، راينهارد (2017)، "1.1 الرسوم البيانية"، نظرية الرسوم البيانية ، نصوص الدراسات العليا في الرياضيات، المجلد 173 ( الطبعة الخامسة)، برلين، نيويورك: سبرينغر-فيرلاغ، ص 3، doi : 10.1007/978-3-662-53622-3 ، ISBN 978-3-662-53621-6.

[6] وودال، د. ر. (1973)، "رقم الربط للرسم البياني ورقم أندرسون الخاص به"، مجلة نظرية التوافيق، السلسلة ب ، 15 (3): 225-255 ، doi : 10.1016/0095-8956(73)90038-5

[7] فان دير هولست، هاين (مارس 2009)، "خوارزمية زمنية متعددة الحدود لإيجاد تضمين بدون روابط للرسم البياني" ، مجلة نظرية التوافيق، السلسلة ب ، 99 (2)، إلسيفير بي في: 512-530 ، doi : 10.1016/j.jctb.2008.10.002

[8] سوداكوف، بيني؛ فوليك، جان (2017)، "نسخ ملونة بشكل صحيح ونسخ قوس قزح من الرسوم البيانية مع عدد قليل من الكرز"، مجلة نظرية التوافيق، السلسلة ب ، 122 (1): 391-416 ، arXiv : 1504.06176 ، doi : 10.1016/j.jctb.2016.07.001.

[9] العمق ، المعهد الوطني للمعايير والتكنولوجيا

[10] براندشتات، أندرياس ؛ لي، فان بانغ؛ سبينراد، جيريمي (1999)، "الفصل 7: الرسم البياني الفرعي المحظور"، فئات الرسوم البيانية: دراسة استقصائية ، سلسلة دراسات SIAM في الرياضيات المتقطعة وتطبيقاتها، الصفحات 105-121 ، ISBN 978-0-89871-432-6

[11] ميتشيم، جون (1969)، "الخصائص الفرعية في الرسوم البيانية"، الجوانب المتعددة لنظرية الرسوم البيانية (وقائع المؤتمر، جامعة غرب ميشيغان، كالامازو، ميشيغان، 1968) ، سلسلة محاضرات في الرياضيات، المجلد 110، سبرينغر، الصفحات 223-230 ، doi : 10.1007/BFb0060121 ، ISBN 978-3-540-04629-5، MR 0253932 .

[NIST_Level-12] المستوى 1 2 ، المعهد الوطني للمعايير والتكنولوجيا

[13] هاريس، جون م. (2000)، التوافقية ونظرية الرسم البياني ، نيويورك: سبرينغر-فيرلاغ، ص 5، ISBN 978-0-387-98736-1

[14] واتس، دنكان جيه؛ ستروغاتز، ستيفن إتش (يونيو 1998)، "الديناميكيات الجماعية لشبكات 'العالم الصغير'"، مجلة نيتشر ، 393 (6684): 440-442 ، رمز Bibcode : 1998Natur.393..440W ، doi : 10.1038/30918 ، PMID 9623998 ، S2CID 4429113

[15] بوندي، جيه إيه (1972)، "نظرية الرسم البياني للأبجدية اليونانية"، نظرية الرسم البياني وتطبيقاتها (وقائع المؤتمر، جامعة ويسترن ميشيغان، كالامازو، ميشيغان، 1972؛ مُهدى إلى ذكرى جيه دبليو تي يونغز) ، سلسلة محاضرات في الرياضيات، المجلد 303، سبرينغر، الصفحات 43-54 ، doi : 10.1007/BFb0067356 ، ISBN 978-3-540-06096-3، MR 0335362

[16] ديستل، راينهارد (2017)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد 173، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، ص 2، doi : 10.1007/978-3-662-53622-3 ، ISBN 978-3-662-53621-6

[17] "نظرية الرسم البياني المتسلسل" ، britannica.com ، تم الاطلاع عليه بتاريخ 25 مارس 2018

[ 1 ]

[

[

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

10 ] على

[ 11 ]

[

[ 13 ]

[ 14 ].

[

[ 16 ]

[

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗