leanprover-community/mathlib4

Tracking Issue: Digraph Targets

Aberta

#26.771 aberto em 5 de jul. de 2025

Ver no GitHubGuia do colaborador
 (7 comentários) (1 reação) (2 responsáveis)Lean (1.592 forks)github user discovery
good first issuet-combinatorics

Métricas do repositório

Stars
 (3.869 estrelas)
Métricas de merge de PR
 (Nenhuma PRs mesclada em 30d)

Description

This is a list of things related to digraphs that would be nice to have.

  • Weak and strong connectivity.

    • If vertices have equal in-degree and out-degree, then the digraph is weakly connected if and only if it is strongly connected.
    • Robbin's Theorem.

  • Tournaments

    • A tournament has a Hamiltonian path.
    • A tournament has a Hamiltonian cycle If and only if it is strongly connected.

Many of the concepts that already exist in SimpleGraph should be ported to Digraph too. Feel free to add digraph results that you would like to see formalized!

Guia do colaborador

Direção de pesquisa
Estude a implementação existente do SimpleGraph no mathlib4 para entender a estrutura e os padrões, depois adapte os para definir Digraph, conectividade fraca e forte e propriedades de torneios.
Pilha de tecnologia
None
Domain
backend
Tipo Issue
Funcionalidade
DifficultyDificuldade de implementação estimada para um novo contribuidor, de 1 para alterações muito pequenas a 5 para trabalho de nível especializado.
3
Tempo estimadoUm intervalo de tempo aproximado para um colaborador experiente investigar, implementar, testar e preparar um pull request.
3-5 dias
Status da atividadeQuão disponível o issue aparece agora: novo, ativo, obsoleto, bloqueado ou aguardando entrada do mantenedor.
Ativo
ClarityCom que clareza o issue explica a mudança esperada, os critérios de aceitação e a próxima etapa.
Claro
Prerequisites
GitLeanGraph theory
Simpatia para novatosUma pontuação de 1 a 100 que estima o quão acessível este issue é para colaboradores iniciantes.
40