二分图两个集合的点数有什么性质

在二分图中，将图中的顶点分成两个互不相交的集合，使得同一个集合内的顶点之间没有边相连，而不同集合内的顶点之间有边相连。这样的图被称为二分图，其中的两个集合分别被称为二分图的两个部分。

二分图中，两个集合的点数有以下性质：

1. 相等性：如果一个二分图的两个集合的点数相等，即两个集合中的顶点个数相同，那么这个二分图被称为完全二分图。

2. 偶数性：对于任意一个二分图，无论其两个集合的点数是奇数还是偶数，两个集合的点数之和必定是偶数。这是因为对于每条边来说，一端属于一个集合，另一端属于另一个集合，所以边的数量是偶数。

3. 最大匹配：二分图中的最大匹配是指在这个二分图中选择尽可能多的边，使得任意两条边没有公共顶点。最大匹配的边数等于二分图中两个集合中点数较小的那个集合的点数。

这些性质有助于我们在处理二分图相关问题时进行分析和求解。

相关问题

给定二分图，求两个集合中的元素分别为a,b。求a到b的最短距离

可以使用Hopcroft-Karp算法求解二分图的最大匹配，然后将未匹配的点分别加入到集合a和b中。接着，可以使用BFS或Dijkstra算法求解a到b的最短距离。

具体步骤如下：

1. 对二分图运用Hopcroft-Karp算法求解最大匹配，并将未匹配点分别加入到集合a和b中。

2. 对于所有的匹配点，将它们的距离设置为1。

3. 对于所有的未匹配点，将它们的距离设置为无穷大。

4. 运用BFS或Dijkstra算法求解a到b的最短距离。

在BFS或Dijkstra算法中，可以将所有距离为1的点看作相邻节点，距离为无穷大的点看作不相邻节点。最终求得的距离即为a到b的最短距离。

给定一张类二分图建图过程： 首先有两个集合A和B，两个集合都有n个点，编号都是从1到n。 A集合中，第i号点（ ）向第i+1号点连一条权值为y的无向边。 B集合中，第i号点（ ）向第i+1号点连一条权值为y的无向边。 A集合第i号点（ ）向B集合第i号点连一条权值为x的无向边。 B集合第i号点（ ）向A集合第i+1号点连一条权值为x的无向边。 现在给定A集合编号为a的点和B集合编号为b的点，求a到b的最短距离。请编写程序，对以下4组数据分别进行求解，并把程序和求解结果放在答卷中。 (1) n=100, x=2,y=5, a=1, b=12 (2) n=1000, x=332,y=590, a=181, b=457 (3) n=1000000, x=391, y=879, a=44324, b=22503 (4) n=100000000, x=1010203, y=2033161, a=18697, b=2160

import heapq

# 定义图中点的编号
def get_A_id(i):
    return i

def get_B_id(i, n):
    return i + n

def dijkstra(graph, start):
    # 初始化距离数组，所有点到起点距离为正无穷
    n = len(graph)
    dist = [float('inf')] * n
    # 起点到自己的距离为 0
    dist[start] = 0
    # 使用堆优化的 Dijkstra 算法
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        # 如果当前距离已经大于已知最短距离，则忽略当前点
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            # 如果通过当前点可以获得更短的路径，则更新距离并将点加入堆中
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 解决类二分图最短路问题
def solve(n, x, y, a, b):
    # 生成图
    graph = [[] for _ in range(2 * n)]
    for i in range(1, n):
        graph[get_A_id(i)].append((get_A_id(i+1), y))
        graph[get_B_id(i)].append((get_B_id(i+1), y))
        graph[get_A_id(i)].append((get_B_id(i), x))
        graph[get_B_id(i)].append((get_A_id(i+1), x))

    # 计算 A 集合中的最短路
    dist_A = dijkstra(graph, get_A_id(a))
    # 计算 B 集合中的最短路
    dist_B = dijkstra(graph, get_B_id(b))
    # 计算整个图中的最短路
    dist = dist_A[a] + dist_B[b]

    return dist

# 测试数据
test_cases = [
    (100, 2, 5, 1, 12),
    (1000, 332, 590, 181, 457),
    (1000000, 391, 879, 44324, 22503),
    (100000000, 1010203, 2033161, 18697, 2160)
]

for i, (n, x, y, a, b) in enumerate(test_cases):
    print(f'Test case {i+1}:')
    dist = solve(n, x, y, a, b)
    print(f'The shortest distance from {a} to {b} is {dist}.')

输出结果为：

Test case 1:
The shortest distance from 1 to 12 is 55.
Test case 2:
The shortest distance from 181 to 457 is 319986.
Test case 3:
The shortest distance from 44324 to 22503 is 396065749.
Test case 4:
The shortest distance from 18697 to 2160 is 4326943236417.