درجه (نظریه گراف)

در نظریه گراف، درجه یک رأس گراف، تعداد یال‌هایی است که به آن رأس متصل هستند. درجه یک رأس همچون ${\displaystyle v}$ را با ${\displaystyle \deg(v)}$ یا ${\displaystyle \deg v}$ نشان می‌دهند. حداکثر درجهٔ یک گراف مانند ${\displaystyle G}$ با نیز با ${\displaystyle \Delta (G)}$ نشان داده می‌شود و مقداری معادل حداکثر مقدار درجهٔ تمام رئوس گراف ${\displaystyle G}$ دارد. حداقل درجهٔ یک گراف با ${\displaystyle \delta (G)}$ نشان داده می‌شود، و مقداری معادل حداقل درجهٔ رئوس گراف ${\displaystyle G}$ دارد.

در یک گراف منتظم، هر رأس درجه یکسانی دارد و بنابراین می‌توانیم از درجهٔ گراف صحبت کنیم. یک گراف کامل (که با ${\displaystyle K_{n}}$ نشان داده می‌شود و ${\displaystyle n}$ در آن تعداد رئوس گراف است) نوع خاصی از گراف منتظم است که در آن همهٔ رئوس حداکثر درجه ممکن (یعنی ${\displaystyle n-1}$) را دارند.

در یک گراف چندگانه، یک حلقه از آنجایی که دو انتهای متصل به رأس دارد، ۲ واحد به درجهٔ یک رأس اضافه می‌کند.

• رأسی با درجه ۰، رأس ایزوله نامیده می‌شود.
• رأسی با درجه ۱، رأس برگ یا رأس انتهایی یا رأس آویز نامیده می‌شود و یالی که با آن رأس برخورد می‌کند، یال آویز نامیده می‌شود. در نمودار سمت راست، {۳٬۵} یک یال آویز است. این اصطلاح در مطالعه درخت‌ها در نظریه گراف و به خصوص درخت‌ها به عنوان ساختار داده رایج است.
• رأسی با درجهٔ n-1 در یک گراف با n رأس، رأس غالب نامیده می‌شود.

• درجه ورودی، درجه خروجی برای دونگاره‌ها
• توزیع مدرک
• دنباله درجه برای گراف‌های دوبخشی

• مشارکت‌کنندگان ویکی‌پدیا. «Degree (graph theory)». در دانشنامهٔ ویکی‌پدیای انگلیسی.
• Erdős, P.; Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal" (PDF). Matematikai Lapok (به مجاری). 11: 264–274..
• Havel, Václav (1955). "A remark on the existence of finite graphs". Časopis Pro Pěstování Matematiky (به چکی). 80 (4): 477–480. doi:10.21136/CPM.1955.108220.
• Hakimi, S. L. (1962). "On realizability of a set of integers as degrees of the vertices of a linear graph. I". Journal of the Society for Industrial and Applied Mathematics. 10 (3): 496–506. doi:10.1137/0110037. MR 0148049..

* Sierksma, Gerard; Hoogeveen, Han (1991). "Seven criteria for integer sequences being graphic". Journal of Graph Theory. 15 (2): 223–231. doi:10.1002/jgt.3190150209. MR 1106533..