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?
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)
Asked: 2020-09-06 13:15:28 +0100
Seen: 390 times
Last updated: Sep 09 '20
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
Is it linked to the vertex connectivity? If so you should look at the function
vertex_connectivityandedge_connectivityin the documentation.Otherwise some ideas for a greedy algorithm:
Subsetsto iterate over all the subsets of vertices of a given size.H = G.copy().H.neighborsto get the neighbors of a given vertex, and thenH.delete_vertexto delete them.H.is_connected.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.