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

תוכן שנמחק תוכן שנוסף
מ הוספת פרק קישורים חיצוניים + תבנית:MathWorld (בערכים בהם אין קישורים חיצוניים) (תג)
שורה 93:
 
== סדרת דרגות ==
'''סדרת הדרגות''' של גרף עם <math>n</math> צמתים וסדר <math>v_1,...,v_n</math> של הצמתים היא הסדרה <math>d(G)=\left(d(v_1),...,d(v_n)\right)</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) המוביל לאלגוריתם להחלטה בזמן פולינומי האם סדרה נתונה היא גרפית.
 
==קישורים חיצוניים==