Ask Your Question
0

Determine whether a graph is connected after deleting all possible sets of specific size.

asked 2020-09-06 13:15:28 +0100

anonymous user

Anonymous

I have a graph of 60 vertices. I want to delete the vertices {u, v, N(u), N(v)} and check whether the resulting graph is connected, where u and v are vertices and N(u) and N(v) are their corresponding neighbors.

How can I write a code that covers all the possibilities?

edit retag flag offensive close merge delete

Comments

Is it linked to the vertex connectivity? If so you should look at the function vertex_connectivity and edge_connectivity in the documentation.

Otherwise some ideas for a greedy algorithm:

  • Use Subsets to iterate over all the subsets of vertices of a given size.
  • For each iteration, make a copy of your graph with H = G.copy().
  • Use H.neighbors to get the neighbors of a given vertex, and then H.delete_vertex to delete them.
  • Then use H.is_connected.
Florentin Jaffredo gravatar imageFlorentin Jaffredo ( 2020-09-07 13:46:02 +0100 )edit

Thank you for your response. My problem is how to write the code? I was thinking of the following Pseudocode: G= graph

V= set of vertices

for i in V, for j in V-{i}

A= G.neighbors(i)

B=G.neighbors(j)

H= G.delete_vertices(A U B)

if H.is_connected()=False

print({i,j})

I don't know how to try this using mathsage.

MKA47 gravatar imageMKA47 ( 2020-09-07 20:46:40 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2020-09-09 17:17:45 +0100

Florentin Jaffredo gravatar image

Are you familiar with Python? I think it's an important prerequisite before learning how to use Sage.

My previous comment almost gave the full answer. If there are some functions you don't know how to use, you can always use ? to access the documentation from a notebook, as well as some examples (e.g. type Subsets? in a cell). Here is a possible solution for some graph G

G = graphs.TutteGraph()
G.relabel()

for U in Subsets(G.vertices(), 2): # iterate over the subsets of vertices of size 2
    H = G.copy() # copy the graph
    H.delete_vertices(flatten([G.neighbors(u, True) for u in U])) # build the list of neighbors of all vertices in the subset and delete them from H
    if not H.is_connected(): # test for connectivity
        print(U)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-09-06 13:15:28 +0100

Seen: 376 times

Last updated: Sep 09 '20