图论邻接矩阵行元素拆分需求：将节点边拆分为多行

算力阿峰

2026-5-19

Alright, let's tackle this adjacency matrix splitting task for your graph theory work. I'll walk through the core logic, give concrete examples, and even share some code snippets to make it actionable.

First, Let's Clarify the Problem

You start with a 3-node adjacency matrix, and you need to split the rows (which represent each node's outgoing edges) into new rows corresponding to sub-nodes:

Row 1 (original node 1) → split into 2 new rows
Row 2 (original node 2) → split into 2 new rows
Row 3 (original node 3) → keep as-is

This will result in a new adjacency matrix with 5 total nodes (2+2+1) — assuming we're splitting original nodes into sub-nodes, not just splitting edges without node changes.

Two Common Splitting Strategies

There are two main ways to handle this, depending on what you need for your graph:

1. Full Inheritance Split

Each sub-node gets the exact same outgoing edges as the original node. This is useful if you want to replicate the original node's connectivity across multiple new nodes.

Example Workflow

Let's use this initial 3×3 matrix as a starting point:

import numpy as np

original_matrix = np.array([
    [0, 1, 1],  # Node 1 connects to Node 2 and 3
    [1, 0, 0],  # Node 2 connects to Node 1
    [0, 1, 0]   # Node 3 connects to Node 2
])

Apply the split rules and build the new matrix:

# Define split rules: original node index → number of sub-nodes
split_rules = {0: 2, 1: 2, 2: 1}

# Build new rows (outgoing edges)
new_rows = []
for node_idx in range(original_matrix.shape[0]):
    num_subnodes = split_rules[node_idx]
    # Copy the original row for each sub-node
    for _ in range(num_subnodes):
        new_rows.append(original_matrix[node_idx].copy())

# For undirected graphs, we need symmetric columns (incoming edges)
new_cols = []
for node_idx in range(original_matrix.shape[1]):
    num_subnodes = split_rules[node_idx]
    for _ in range(num_subnodes):
        new_cols.append(original_matrix[:, node_idx].copy())

# Combine rows and columns into the final matrix
new_matrix = np.column_stack(new_cols)
new_matrix = np.row_stack(new_rows)

print("Full Inheritance Split Result:")
print(new_matrix)

Output

Full Inheritance Split Result:
[[0 1 1 1 1]
 [0 1 1 1 1]
 [1 0 0 0 0]
 [1 0 0 0 0]
 [0 1 1 0 0]]

2. Random Edge Distribution Split

If you want to distribute the original node's edges randomly among its sub-nodes (instead of copying all edges), this approach works. It's great for simulating node fragmentation where sub-nodes take on partial connectivity.

Code Implementation

import numpy as np
import random

original_matrix = np.array([
    [0, 1, 1],
    [1, 0, 0],
    [0, 1, 0]
])

split_rules = {0: 2, 1: 2, 2: 1}

# Build new rows (outgoing edges)
new_rows = []
for node_idx in range(original_matrix.shape[0]):
    num_subnodes = split_rules[node_idx]
    # Get indices of nodes the original node connects to
    original_edges = np.where(original_matrix[node_idx] == 1)[0]
    # Randomly assign edges to sub-nodes
    edge_groups = [[] for _ in range(num_subnodes)]
    for edge in original_edges:
        edge_groups[random.randint(0, num_subnodes-1)].append(edge)
    # Create rows for each sub-node
    for group in edge_groups:
        new_row = np.zeros(original_matrix.shape[1], dtype=int)
        for edge in group:
            new_row[edge] = 1
        new_rows.append(new_row)

# Handle columns for undirected graphs
new_cols = []
for node_idx in range(original_matrix.shape[1]):
    num_subnodes = split_rules[node_idx]
    original_edges = np.where(original_matrix[:, node_idx] == 1)[0]
    edge_groups = [[] for _ in range(num_subnodes)]
    for edge in original_edges:
        edge_groups[random.randint(0, num_subnodes-1)].append(edge)
    for group in edge_groups:
        new_col = np.zeros(original_matrix.shape[0], dtype=int)
        for edge in group:
            new_col[edge] = 1
        new_cols.append(new_col)

# Assemble final matrix
new_matrix = np.column_stack(new_cols)
new_matrix = np.row_stack(new_rows)

print("Random Edge Distribution Split Result (Example):")
print(new_matrix)

Sample Output

Random Edge Distribution Split Result (Example):
[[0 1 0 1 0]
 [0 0 1 0 1]
 [1 0 0 0 0]
 [0 0 0 0 0]
 [0 1 0 0 0]]

Key Notes

Directed vs Undirected Graphs: If you're working with directed graphs, you don't need to mirror the split in columns — only handle the rows (outgoing edges).
Custom Rules: Instead of random distribution, you can hardcode which edges go to which sub-nodes if you have specific requirements.
New Node Count: The total number of new nodes is the sum of your split counts (2+2+1=5 in this case), so the final matrix will be 5×5.

内容的提问来源于stack exchange，提问作者MsCurious