Problem 54074. Determining if a Degree Sequence is Potentially a Graph

Created by Nicholas Deary

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>A degree sequence is a list of numbers representing the degrees of vertices in a graph. While it is difficult to tell if a graph can be made from a degree sequence, there are some ways to tell for certain that a graph does not exist with a given degree sequence. One easy first check is the following: </w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>First, sort the degree sequence in descending order. Next, pop the first degree off the list and subtract one from the next N elements, where N is the degree you popped off. Repeat until the list is empty. If at any point a degree in the list is less than 0 or if there are not N elements left in the list to subtract from, there is no graph that exists with that degree sequence.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Write a function </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>is_graph </w:t></w:r><w:r><w:t>that returns true if this algorithm results in an empty list or false if it fails at any point.</w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(232, 230, 227); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(232, 230, 227); white-space: normal; "><div style="block-size: 166.5px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 83.25px; transform-origin: 407px 83.25px; vertical-align: baseline; "><div style="block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 376.783px 8px; transform-origin: 376.783px 8px; unicode-bidi: normal; "><span style="">A degree sequence is a list of numbers representing the degrees of vertices in a graph. While it is difficult to tell if a graph can be made from a degree sequence, there are some ways to tell for certain that a graph does not exist with a given degree sequence. One easy first check is the following: </span></span></div><div style="block-size: 63px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 31.5px; text-align: left; transform-origin: 384px 31.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 379.867px 8px; transform-origin: 379.867px 8px; unicode-bidi: normal; "><span style="">First, sort the degree sequence in descending order. Next, pop the first degree off the list and subtract one from the next N elements, where N is the degree you popped off. Repeat until the list is empty. If at any point a degree in the list is less than 0 or if there are not N elements left in the list to subtract from, there is no graph that exists with that degree sequence.</span></span></div><div style="block-size: 22.5px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 11.25px; text-align: left; transform-origin: 384px 11.25px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 50.4333px 8px; transform-origin: 50.4333px 8px; unicode-bidi: normal; "><span style="">Write a function </span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 37.8px 8px; transform-origin: 37.8px 8px; unicode-bidi: normal; "><span style="font-family: Menlo, Monaco, Consolas, &quot;Courier New&quot;, monospace; perspective-origin: 37.8px 8.5px; transform-origin: 37.8px 8.5px; ">is_graph </span></span><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 259.8px 8px; transform-origin: 259.8px 8px; unicode-bidi: normal; "><span style="">that returns true if this algorithm results in an empty list or false if it fails at any point.</span></span></div></div></div>

Solve

Solution Stats

24 Solutions
7 Solvers

Last Solution submitted on May 30, 2022

Last 200 Solutions

Problem Recent Solvers7

Problem Tags

degree sequence graphs

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!