마트로이드 계급

매트로이드의 수학적 이론에서 매트로이드의 순위는 매트로이드에 있는 독립된 세트의 최대 크기다.매트로이드 원소의 부분 집합 S의 순위는 유사하게 S의 독립된 부분 집합의 최대 크기이며, 매트로이드 원소의 순위 맵 세트의 순위는 그 순위에 대한 요소 집합의 순위 기능이다.

순위 함수는 매트로이드를 공리화할 수 있는 매트로이드 이론의 기본 개념 중 하나이다.매트로이드 순위 함수는 하위 모듈 세트 함수의 중요한 하위 클래스를 형성한다.비방향 그래프, 행렬 및 필드 확장과 같은 특정 유형의 수학 개체에서 정의된 매트로이드의 순위 기능은 해당 개체의 연구 내에서 중요하다.

예

모든 예에서 E는 매트로이드의 기본 집합이고, B는 E의 일부 하위 집합이다.

• 독립 집합이 모두 E의 하위 집합인 M을 자유 매트로이드로 한다.그렇다면 M의 순위 함수는 간단히 r(B) = B이다.
• M을 균일한 매트로이드로 두십시오. 여기서 독립 집합은 일부 정수 k에 대해 최대 k 원소를 가진 E의 하위 집합입니다.M의 순위 함수는 r(B) = 최소(k, B )이다.
• M을 칸막이 매트로이드로 하자: E의 요소는 범주로 분할되고, 각 범주 c는 용량 k를_c 가지며, 독립 집합은 범주 c의 최대 k 요소를_c 포함하는 것이다.M의 순위 함수는 r(B) = sum_c min(k_c, B )이며_c 여기서 B는_c 범주 c에 포함된 부분 집합 B이다.
• M을 그래픽 매트로이드로 두십시오. 여기서 독립 집합은 일부 고정되지 않은 그래프 G의 모든 반복 에지 집합(포리스트)입니다.그 다음 순위 함수 r(B)는 그래프에서 B의 연결된 성분(단일 버텍스 성분 포함) 수를 뺀 정점 수입니다.

특성 및 공리화

매트로이드의 순위 함수는 다음과 같은 특성을 준수한다.

(R1) 순위함수의 값은 항상 음이 아닌 정수이며 빈 집합의 순위는 0이다.

(R2) For any two subsets ${\displaystyle A}$ and ${\displaystyle B}$ of ${\displaystyle E}$, ${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$. That is, the rank is a submodular set function.

$($R3) 모든 세트 $A{\displaystyle }$ ${\displaystyle$ $A$$}$ 및 요소$$ $x{\displaystyle }$ ${\displaystyle$ x${\displaystyle \},<img\; alt="x"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4"\; style="vertical-align:\; -0.338ex;\; width:1.33ex;\; height:1.676ex;"\; papago-attr-id="57">}$ ${\displaystyle r}$( A${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle r}$(${\displaystyle A}$)${\displaystyle }$+ 1 ${\displaystyle r(A)\leq$ r$(A)\leq r(A)+1}.$

These properties may be used as axioms to characterize the rank function of matroids: every integer-valued submodular set function on the subsets of a finite set that obeys the inequalities ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$ for all ${\displaystyle A}$ and ${\displaystyl$$e x}$은(는) 매트로이드의 순위 함수다.^[1][2]

위의 속성은 추가 속성을 의미한다.

• $A{\displaystyle }$ ${\displaystyle \subset }$ ${\displaystyle B}$ ${\displaystyle \subset }$ ${\displaystyle E}$ ${\displaystyle$A$\subset B$ $r{\displaystyle }$ (${\displaystyle A}$) ${\displaystyle \le }$ ${\displaystyle r}$( ${\displaystyle B}$) ${\displaystyle \le }$ ${\displaystyle r}$ ${\displaystyle (E}$) ${\displaystyle r(A)\leq r(B)\leq r(E$ 즉, 순위는 단조함수다.
• ${\displaystyle r}$( ${\displaystyle A}$) ${\displaystyle \le }$ A $displaystyle r(A)\leq$A $\}.$

순위의 기타 행렬 특성

순위 함수는 매트로이드의 다른 중요한 특성을 결정하는 데 사용될 수 있다.

• 세트는 순위가 카디널리티와 동일한 경우에만 독립적이며, 순위보다 카디널리티가 큰 경우에만 종속된다.^[3]
• 비빈 집합은 카디널리티가 1에 랭크를 더한 값이고 세트에서 한 요소를 제거하여 형성된 모든 하위 집합이 동일한 순위를 갖는 회로다.^[3]
• 세트는 그 순위가 카디널리티와 매트로이드의 순위 둘 다와 같다면 기준이 된다.^[3]
• 한 세트는 같은 순위를 유지하면서 그 위에 추가할 수 있는 다른 요소가 존재하지 않는다는 점에서 그 등급에 대해 최대치라면 닫힌다.
• ${\displaystyle A}$- ${\displaystyle r}$( ${\displaystyle A}$) ${\displaystyle$ A$(A)}$의 차이를 서브셋 $A{\displaystyle }$ ${\displaystyle A}$의 nullity라고 하며$$$,$ 독립 세트를 얻기 위해$$ $A{\displaystyle }$ ${\displaystyle A}$에서 제거해야 하는 최소 요소 수입니다.^[4]
• The corank of a subset ${\displaystyle A}$ can refer to at least two different quantities: some authors use it to refer to the rank of ${\displaystyle A}$ in the dual matroid, ${\displaystyle r^{*}(A)= A +r(E\setminus A)-r(E)}$, while other authors use corank to refer to the dipion $r{\displaystyle }$( ${\displaystyle E}$)${\displaystyle }$- ${\displaystyle r}$( A${\displaystyle }$) ${\displaystyle r(E)-r(A)}$.

특수 매트리스의 순위

그래프 이론에서, 그래프의 회로 순위(또는 사이클로 숫자)는 연관된 그래픽 매트로이드의 코랭크로, 나머지 가장자리가 숲을 이루도록 하기 위해 그래프에서 제거해야 하는 최소 가장자리 수를 측정한다.^[5]몇몇 저자들은 이 숫자로 매개변수화된 그래프 알고리즘의 매개변수화된 복잡성을 연구했다.^[6][7]

선형대수학에서 행렬의 열로부터 선형 독립에 의해 정의되는 선형 매트로이드의 순위는 행렬의 순위로,^[8] 또한 열에 의해 확장되는 벡터 공간의 차원이기도 하다.

추상대수학에서, 대수적 독립성에 의한 필드 확장 L/K의 요소 집합으로부터 정의되는 매트로이드의 순위를 초월도라고 한다.^[9]

효용 함수의 매트로이드 순위 함수

매트로이드 순위함수(MRF)는 공정한 항목 할당 문제에서 에이전트의 효용 함수를 나타내기 위해 사용되어 왔다.에이전트의 효용 기능이 MRF인 경우, 다음을 의미한다.

• 대리점의 효용성은 수익 감소(MRF가 하위 모델 함수라는 사실에 따른 것이다)
• 각 항목에 대한 에이전트의 한계 효용은 이분법(이진법) - 0 또는 1이다.즉, 번들에 항목을 추가하면 유틸리티가 추가되지 않거나 1의 유틸리티가 추가된다.

이 설정에 대해 알려진 솔루션은 다음과 같다.

• Babaioff, Ezra 및 Feige는^[10] Prioritized Egalitic이라 불리는 결정론적 다항식 시간 진실성 메커니즘을 설계하여, 결과적으로 또한 EFX인₀ 로렌츠 지배적 할당을 출력하여 유틸리티의 생산물을 최대화하고 1/2-fraction 최대 점유율을 달성하며, 가치가 추가되었을 때 최대 점유율을 획득한다.무작위적인 우선 순위에 따라, 이 메커니즘은 이전의 질투심도 없다.또한 한계 효용이 양성이 아니거나 [1,1+e] 범위 내에 있는 전자 편차 평가도 연구한다.
• Benabbou, Chakraborty, 이가라시와 Zick[11]은, 이 설정에, 모든 Pareto-optimal 할당 전력 회사의 합, 모든max-sum 분배에 대한 대칭strictly-concave 기능 f을 극대화 분배의 집합 f의 선택에 이 모든f-maximizing 할당은 EF의존하지 않는다(실용적인 복지)를 극대화를 보여 준다.1.이는 최대 제품 할당이 렉시민-최적 할당이며, 모두 최대값과 EF1임을 의미한다.또한 최대합과 EF1 할당을 계산하는 다항식 시간 알고리즘(오목함수를 반드시 최대화하는 것은 아님), 초당적 그래프에서 최대 카디널리티 매칭을 바탕으로 MRF의 특수한 경우에 대해 오목함수를 최대화하는 다항식 시간 알고리즘을 제시한다.

매트로이드 순위 함수는 총 대체 평가의 하위 등급이다.

참고 항목

• 랭크오라클

참조