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

תוכן שנמחק תוכן שנוסף
Eissie (שיחה | תרומות)
מאין תקציר עריכה
Eissie (שיחה | תרומות)
קישור
שורה 30:
'''סדרת הדרגות''' של גרף <math>G=\left(V, E\right)</math> עם <math>n</math> צמתים <math>v_1,...,v_n</math> היא הסדרה <math>d(G)=\left(d(v_1),...,d(v_n)\right)</math> כאשר <math>d(v_i)</math> היא הדרגה של צומת <math>v_i</math>.
 
סדרה נקראת '''גרפית''' אם היא סדרת הדרגות של איזשהו גרף. קיים אפיון של הסדרות הגרפיות ([[פאול ארדש|Erdős]] and Gallai, 1960<ref>{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}</ref>) המוביל לאלגוריתם פולינומיאלי להחלטה האם סדרה נתונה היא גרפית.
 
== ראו גם ==