ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
מ הערות שוליים
מ ←‏סדרת דרגות: ניסוח ועריכה
שורה 93:
 
== סדרת דרגות ==
[[קובץ:Conjugate-dessins.svg|ממוזער|זוג גרפים לא איזומורפים עם אותה סדרת דרגות (3,2,2,2,2,1,1,1).]]
'''סדרת הדרגות''' של גרף עם <math>n</math> צמתים וסדר <math>v_1,...,v_n</math> של הצמתים היא הסדרה <math>d(G)=\left(d(v_1),...,d(v_n)\right)</math>. סדרה נקראת '''גרפית''' אם היא סדרת הדרגות של איזשהו גרף.
'''סדרת הדרגות''' של גרף לא מכוון עם <math>n</math> צמתים היא סדרה לא עולה של דרגות הצמתים של הגרף.
 
לגרפים איזומורפים יש את אותה סדרת דרגות. אבל התכונה ההפוכה לא מתקיימת, אם לשני גרפים אותה סדרת דרגות הם לא בהכרח איזומורפיים.
קיים אפיון של הסדרות הגרפיות (<ref>{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}</ref> [[פאול ארדש|Erdős]] and Gallai, 1960) המוביל לאלגוריתם להחלטה בזמן פולינומי האם סדרה נתונה היא גרפית.▼
 
▲סדרה נקראת '''גרפית''' אם היא סדרת הדרגות של איזשהו גרף. קיים אפיון של הסדרות הגרפיות (<ref>{{הערה|{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}</ref> [[פאול ארדש|Erdős]] and Gallai, 1960)}} המוביל לאלגוריתם להחלטה בזמן פולינומי האם סדרה נתונה היא גרפית.
 
==קישורים חיצוניים==
אוחזר מתוך "https://he.wikipedia.org/wiki/דרגה_(תורת_הגרפים)"