build_cut_random {gor}

Random cut generation on a graph

Description

Random cut generation on a graph. This function generates a hopefully large cut on a graph by randomly selecting vertices; it does not attempt to maximize the cut size or weigth, so it is intended to be used as part of some smarter strategy.

Usage

build_cut_random(G, w = NA)

Arguments

G

Graph

w

Weight matrix (defaults to NA). It should be zero for those edges not in G

Details

It selects a random subset of the vertex set of the graph, computing the associated cut, its size and its weigth, provided by the user as a weight matrix. If the weight argument w is NA, the weights are taken as 1.

Value

A list with four components: $set contains the subset of V(g) representing the cut, $size contains the number of edges of the cut, $weight contains the weight of the cut (which coincides with $size if w is NA) and $cut contains the edges of the cut, joining vertices inside $set with vertices outside $set.

Author(s)

Cesar Asensio

See Also

build_cut_greedy builds a cut using a greedy algorithm, compute_cut_weight computes cut size, weight and edges, improve_cut_flip uses local search to improve a cut obtained by other methods, plot_cut plots a cut.

Examples

## Example with known maximum cut
K10 <- make_full_graph(10)   # Max cut of size 25
c0 <- build_cut_random(K10)
c0$size  # Different results: 24, 21, ...
plot_cut(c0, K10)

## Max-cut of a random graph
set.seed(1)
n <- 25
g <- sample_gnp(n, p=0.25)
c1 <- build_cut_random(g)   # Repeat as you like
c1$size  # Different results: 43, 34, 39, 46, 44, 48...
plot_cut(c1, g)