Problem 5: Adjacent states

Write code in Python, Sagemath

Grading criteria: correctness of code.

Throughout this problem, by "US states" we mean the 50 US states plus the District of Columbia.

5a. The following string, adapted from this source, represents the adjacencies among US states, as represented by their standard postal abbreviations.

Starting from s, construct a graph whose vertices are labeled by the postal abbreviations, with an edge between two vertices if and only if they correspond to adjacent states.

define s:

s = """ AK AL,MS,TN,GA,FL AR,MO,TN,MS,LA,TX,OK AZ,CA,NV,UT,NM CA,OR,NV,AZ CO,WY,NE,KS,OK,NM,UT CT,NY,MA,RI DC,MD,VA DE,MD,PA,NJ FL,AL,GA GA,FL,AL,TN,NC,SC HI IA,MN,WI,IL,MO,NE,SD ID,MT,WY,UT,NV,OR,WA IL,IN,KY,MO,IA,WI IN,MI,OH,KY,IL KS,NE,MO,OK,CO KY,IN,OH,WV,VA,TN,MO,IL LA,TX,AR,MS MA,RI,CT,NY,NH,VT MD,VA,WV,PA,DC,DE ME,NH MI,WI,IN,OH MN,WI,IA,SD,ND MO,IA,IL,KY,TN,AR,OK,KS,NE MS,LA,AR,TN,AL MT,ND,SD,WY,ID NC,VA,TN,GA,SC ND,MN,SD,MT NE,SD,IA,MO,KS,CO,WY NH,VT,ME,MA NJ,DE,PA,NY NM,AZ,CO,OK,TX NV,ID,UT,AZ,CA,OR NY,NJ,PA,VT,MA,CT OH,PA,WV,KY,IN,MI OK,KS,MO,AR,TX,NM,CO OR,CA,NV,ID,WA PA,NY,NJ,DE,MD,WV,OH RI,CT,MA SC,GA,NC SD,ND,MN,IA,NE,WY,MT TN,KY,VA,NC,GA,AL,MS,AR,MO TX,NM,OK,AR,LA UT,ID,WY,CO,AZ,NV VA,NC,TN,KY,WV,MD,DC VT,NY,NH,MA WA,ID,OR WI,MI,MN,IA,IL WV,OH,PA,MD,VA,KY WY,MT,SD,NE,CO,UT,ID """

# your code goes here

5b. Compute a maximum flow and a minimum cut for this graph, using California as the source and the District of Columbia as the sink.

# your code goes here