How to Find a Maximal Subset of X in V=C[0,1]?

Thread starter laminatedevildoll
Start date May 10, 2005
Tags

Independent

In summary, a maximal independent subset is a subset of elements within a larger set that are not connected or related to each other. It is different from a maximum independent set in that it may not be the largest possible independent set, but it is the largest within the given set. In graph theory, a maximal independent subset is useful for determining the maximum independent set of a graph. It can be found efficiently for certain types of graphs, but is an NP-hard problem for general graphs. A maximal independent subset is closely related to concepts such as vertex cover and clique in graph theory.

May 10, 2005

laminatedevildoll

Let V=C[0,1] be the vector space for all-real valued continuous functions on [0,1]. If X={1,cosx,cos2x, cos3x, cos^2x, cos^3x}. How do I find a maximal subset of X?

Physics news on Phys.org

May 10, 2005

HallsofIvy

Science Advisor

Homework Helper

Use trigononometric identities. cos²x= (1/2)(1+ cos(2x)) and sin(²x= (1/2)(1- sin(2x)). You can find a similar identity for cos³(x).

May 10, 2005

laminatedevildoll

Thank you.

1. What is a maximal independent subset?

A maximal independent subset is a set of elements within a larger set that are not connected or related to each other in any way. This means that no element in the subset can be removed without breaking the independence of the remaining elements.

2. How is a maximal independent subset different from a maximum independent set?

A maximal independent subset is a subset of a larger set, while a maximum independent set is the largest possible independent set within a given set. In other words, a maximal independent subset may not be the largest possible independent set, but it is the largest within the given set.

3. How is a maximal independent subset useful in graph theory?

In graph theory, a maximal independent subset can be used to determine the maximum independent set of a graph. This is important in applications such as scheduling, where tasks must be completed without any dependencies or conflicts.

4. Can a maximal independent subset be found efficiently?

Finding a maximal independent subset can be done in polynomial time for certain types of graphs, such as bipartite graphs. However, for general graphs, it is an NP-hard problem, meaning that it cannot be solved efficiently for all inputs.

5. How is a maximal independent subset related to other graph theory concepts?

A maximal independent subset is closely related to concepts such as vertex cover and clique. A vertex cover is a set of vertices that covers all edges in a graph, while a clique is a set of vertices where every pair of vertices is connected. A maximal independent subset can be thought of as the complement of a vertex cover, and the intersection of a maximal independent subset and a clique is always empty.