|
|
|
'''סדרת הדרגות''' של גרף לא מכוון עם <math>n</math> צמתים היא סדרה לא עולה של דרגות הצמתים של הגרף.
לגרפים איזומורפים יש את אותה סדרת דרגות. אבל התכונה ההפוכה לא מתקיימת, אם לשני גרפים אותה סדרת דרגות הם לא בהכרח איזומורפיים.
סדרה נקראת '''גרפית''' אם היאקיים גרף שהיא סדרת הדרגות שלשלו. איזשהו'''בעיית סדרת הדרגות''' היא למצוא גרף (או את כל הגרפים) שסדרת הדרגות שלו שווה לסדרה נתונה כלשהי. קיים אפיון של הסדרות הגרפיות {{אנ|Erdős–Gallai theorem}}{{הערה|{{צ-מאמר|מחבר=P. Erdős, T. Gallai|שם=Graphs with prescribed degrees of vertices|כתב עת=Mat. Lopak|כרך=11|עמ=264-274|שנת הוצאה=1960}}}} המוביל לאלגוריתם להחלטההחלטה בזמן פולינומי האם סדרה נתונה היא גרפית והגרף הוא גרף פשוט (אם הגרף יכול להכיל לולאות וקשתות מקבילות ניתן לבנות גרף שכזה לכל סדרה לא יורדת שסכומה זוגי, ולא ניתן לבנות גרף שכזה לכל סדרה שסכומה אי-זוגי (נובע ישירות מ[[למת לחיצות הידיים]])).
==קישורים חיצוניים==
|
