%run "W3D4functions.ipynb"
You are given a graph and two vertices. Check if they are neigbours. Recall that two vertices are neighbors if they are connected by an edge.
For example, for G=[[1,2,3],[0],[0,4,5],[0],[2,5],[2,4]], x=2, y=5
it should return True
def neighbours(G, x, y):
# Complete the function. G is a graph adjacency list, x and y are numbers of vertices
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 2
y = 5
check(neighbours(G, x, y), correct_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 5
y = 2
check(neighbours(G, x, y), correct_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 3
y = 2
check(neighbours(G, x, y), correct_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 0
y = 4
check(neighbours(G, x, y), correct_neighbours(G, x, y))
G = [[1, 3], [], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 0
y = 2
check(neighbours(G, x, y), correct_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 2
y = 2
check(neighbours(G, x, y), correct_neighbours(G, x, y))
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
You are given a graph and two vertices. Check if they are distance two apart. For example, on the picture below vertices 1 and 2 are distance two apart while 3 and 4 are not and 4 and 5 are not because they are neighbours.
For example, we need to solve this problem to find out whether people $x$ and $y$ have mutual friends.
For example, for G=[[1,2,3],[0],[0,4,5],[0],[2,5],[2,4]], x=2, y=3
it should return True
.
Be sure you have checked all the corner cases
def almost_neighbours(G, x, y):
# Complete the function. G is a graph adjacency list, x and y are numbers of vertices
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 2
y = 5
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 3
y = 2
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 0
y = 4
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 1
y = 5
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
G = [[1, 3], [], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 0
y = 2
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
G = [[1, 2, 3], [0], [0, 4, 5], [0], [2, 5], [2, 4]]
x = 2
y = 2
check(almost_neighbours(G, x, y), correct_almost_neighbours(G, x, y))
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
Consider a graph with $N$ vertices numbered from 1 to $N$ and without edges, $N\geq3$. You need to make it connected (every vertice should be reachable from each other) in a such way that sums of numbers of vertices adjacent to each vertice are equal.
Below you can see such graph for $N=3$.
Here each vertice has sum of nubers of adjacent vertices equals to 3.
For example for the graph above solve(3)
may return [[], [3], [3], [1, 2]]
.
Hint: solve the problem for even values of $N$ first
def solve(n):
# Complete the function. It should return the graph adjacency list of size n+1, with an empty first list.
n = 3
check(solve(n), correct_solve(n))
n = 4
check(solve(n), correct_solve(n))
n = 5
check(solve(n), correct_solve(n))
n = 6
check(solve(n), correct_solve(n))
n = 49
check(solve(n), correct_solve(n))
n = 50
check(solve(n), correct_solve(n))
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!