ויקיפדיה

צומת (תורת הגרפים) – הבדלי גרסאות

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
מ הוספת פרק קישורים חיצוניים + תבנית:MathWorld (בערכים בהם אין קישורים חיצוניים) (תג) (דיון)
מ ניסוח
שורה 1:
[[קובץ:6n-graf.svg|שמאל|ממוזער|גרף לא מכוון בעל 6 קודקודים ו-7 קשתות]]
ב[[תורת הגרפים]], '''צומת''' או '''קודקוד''' (ב[[אנגלית]]: '''vertexVertex''') הוא יחידת היסוד ממנה מורכב ה[[גרף (תורת הגרפים)|גרף]]. גרף לא מכוון מורכב מזוגות לא סדורים של קודקודים, וגרף מכוון מורכב מ[[זוג סדור|זוגות סדורים]] של קודקודים (כלומר, יש משמעות לכיוון של הקשתות המחברות אתקבוצת הקודקודים. כלבגרף קשתמסומנת יוצאתבאות מקודקוד<math>\ אחד ונכנסת לקודקוד שני)V</math>.
 
גרף מכוון מורכב מ[[זוג סדור|זוגות סדורים]] של קודקודים וגרף לא מכוון מורכב מזוגות לא סדורים של קודקודים. לפיכך, יש משמעות לכיוון הקשתות המחברות את הקודקודים. כל קשת יוצאת מקודקוד אחד ומתחברת לקודקוד שני.
[[דרגה (תורת הגרפים)|דרגה]] של קודקוד בגרף לא מכוון שווה למספר הקשתות המחברות אותו עם קודקודים אחרים. בגרף מכוון, דרגת הכניסה של קודקוד שווה למספר הקשתות הנכנסות אליו, ודרגת היציאה שווה למספר הקשתות היוצאות ממנו. ▼
 
▲[[דרגה (תורת הגרפים)|דרגה]] של קודקוד בגרף לא מכוון שווה למספר הקשתות המחברות אותו עם קודקודים אחרים. בגרף מכוון, דרגת הכניסה של קודקוד שווה למספר הקשתות הנכנסות אליו, ודרגת היציאה שווה למספר הקשתות היוצאות ממנו.
גרף k - צביע הוא גרף הניתן לצביעה ב k צבעים כך שכל שני צמתים המחוברים בקשת צבועים בצבע שונה.▼
 
▲גרף k - צביע הוא גרף הניתן לצביעה ב -k צבעים כך שכל שני צמתים המחוברים בקשת צבועים בצבע שונה.{{תורת הגרפים}}
קבוצת הקודקודים בגרף מסומנת באות <math>\ V</math>.
{{תורת הגרפים}}
==קישורים חיצוניים==
* {{MathWorld}}
אוחזר מתוך "https://he.wikipedia.org/wiki/צומת_(תורת_הגרפים)"