Extremal Choices¶

Properties¶

• No vertex outside the path is connected to two vertices within the path that are 3 or more edges apart

• As a corollary of the above proposition, any external vertex is connected to at most 3 vertices within this path

• The induced subgraph of the vertices in this path is the path itself, with no additional edges present

Note: The original RST structure with tildes and hyphens has been preserved exactly. No code blocks or special formatting elements were present in the input text to modify.

Properties¶

• All vertices adjacent to the start and end vertices of this path are contained within the path.

• No two consecutive vertices share a common neighbor outside the path.

• If the start and end of this path are connected, the path contains all vertices of its component.

Algorithm Workflow¶

1. For each vertex in the graph:

   • Perform BFS starting from that vertex.

   • Track the distance from the starting vertex to other vertices.

   • If a back edge to the starting vertex is found, calculate the cycle length.

2. The smallest length among all detected cycles is the graph's shortest cycle.

Code Example¶

def find_smallest_cycle(graph):
    # Function to find the smallest cycle using BFS
    min_length = float('inf')
    for vertex in graph.vertices:
        distances = {v: -1 for v in graph.vertices}
        parent = {v: None for v in graph.vertices}
        queue = deque()
        distances[vertex] = 0
        queue.append(vertex)

        while queue:
            current = queue.popleft()
            for neighbor in graph.neighbors(current):
                if distances[neighbor] == -1:
                    distances[neighbor] = distances[current] + 1
                    parent[neighbor] = current
                    queue.append(neighbor)
                elif parent[current] != neighbor:
                    # Detect a cycle and update min_length
                    cycle_length = distances[current] + distances[neighbor] + 1
                    min_length = min(min_length, cycle_length)
    return min_length if min_length != float('inf') else -1

Important Notes¶

• In directed graphs, back edges must be checked carefully to avoid false cycles.

• The time complexity of this algorithm is O(V*(V+E)), where V is the number of vertices and E the number of edges.

Properties¶

• The induced subgraph of the vertices of this cycle is the cycle itself, with no additional edges present.

• If the length of this cycle is greater than 4, each vertex outside this cycle has at most one edge connecting it to a vertex within the cycle.

Properties¶

• The induced subgraph of the vertices of this cycle is the cycle itself, containing no additional edges.

• If the length of this cycle is greater than three, each vertex outside the cycle is connected to at most two vertices of the cycle.

The lowest leaf in a rooted tree refers to the leaf with the maximum height.

Example code for finding the lowest leaf:

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

def find_lowest_leaf(root):
    # Traverse the tree recursively
    max_height = -1
    lowest_leaf = None

    def dfs(node, current_height):
        nonlocal max_height, lowest_leaf
        if not node.children:  # Leaf node
            if current_height > max_height:
                max_height = current_height
                lowest_leaf = node
        else:
            for child in node.children:
                dfs(child, current_height + 1)

    dfs(root, 0)
    return lowest_leaf  # Return the leaf with maximum height

Note: The term "lowest leaf" might seem contradictory since it actually has the greatest distance (height) from the root. This concept is important in algorithms related to calculating tree height and balance.

Properties¶

• All children of this leaf node's parent are leaves.